python/TangDou/AcWing/CheckCircle/HDU1272【DFS】.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N << 1;
/*
7e5+10
=700000*4/1024/1024=2.67MB
这内存也不大啊，为啥会SE呢？不是说64MB的上限吗?
被卡的好难受，这是逼我去用并查集+公式解题啊！
*/
//邻接表
int e[M], h[N], idx, ne[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool st[N];  //标识某个节点号是不是使用过
bool vis[N]; //是不是在dfs过程中搜索过
int flag;    // true:满足两个条件 false:不满足两个条件 (1)是不是有环，要求无环 (2)是不是连通，要求连通

// dfs无向图判环
void dfs(int u, int fa) {               //从u节点开始搜索，它的父节点是fa，输入fa的意义在于不能走回头路，防止死循环
    vis[u] = true;                      //标识u已经搜索过了
    for (int i = h[u]; ~i; i = ne[i]) { //枚举u的每一条出边
        int j = e[i];
        if (j == fa) continue; //放过来源节点
        if (vis[j]) {          //如果j被搜索过，说明有环
            flag = false;      //标识有环
            return;
        }
        dfs(j, u); //继续搜索j节点，它的父节点是u
    }
}
//每组输入的清空与初始化
void init() {
    memset(st, 0, sizeof(st));
    memset(vis, 0, sizeof(vis));
    memset(h, -1, sizeof h);
    idx = 0;
}

int main() {
    int a, b;
    init();
    while (scanf("%d%d", &a, &b) && ~a && ~b) {
        if (a && b) {                   //如果输入的a,b是两个非零数字
            st[a] = st[b] = true;       //标识a,b已使用
            add(a, b), add(b, a);       //添加两条无向边
        } else {                        //如果输入的是两个0,描述是一组数据输入结束
            flag = true;                //默认是无环+连通图
            // 1、检查是不是无环
            for (int i = 1; i < N; i++) //枚举每个节点
                if (st[i]) {            //如果i节点使用过
                    //从找到的第一个使用过的节点开始进行dfs扫描
                    dfs(i, i);
                    break;
                }
            // 2、检查连通性
            if (flag) { //扫描完的结果：1、找到了环，2、没有找到环
                //下面将现次枚举每个使用过的点,查看它是不是在dfs过程中被扫描到了，如果存在使过未扫到的点，则说明不连通
                for (int i = 1; i < N; i++)
                    if (st[i] && !vis[i]) { //如果存在出现过，但dfs没有扫描到的点，说明不连通
                        flag = false;
                        break;
                    }
            }
            flag ? puts("Yes") : puts("No"); //两个条件都满足，输出Yes,否则输出No
            init();                          //因为要输入下一组数据，需要清空状态数组
        }
    }
    return 0;
}