python/TangDou/AcWing/CheckCircle/HDU3342【DFS判环】.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = N << 1;

//邻接表
int e[M], h[N], idx, ne[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int color[N]; // 染色法数组： 0:还没有访问过 1:正在访问中 2:它及它的子节点都已经访问过
int n, m;     // n个顶点，m条边

bool dfs(int u) {
    color[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (color[j] == 1) return true;
        if (color[j] == 0 && dfs(j)) return true;
    }
    color[u] = 2;
    return false;
}

int main() {
    while (~scanf("%d%d", &n, &m) && n) {
        memset(h, -1, sizeof(h));        //多组测试数据，每次输入清空地图
        memset(color, 0, sizeof(color)); //多组测试数据，每次输入清空染色法数组
        idx = 0;

        for (int i = 1; i <= m; i++) { //有向图，m条边
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
        }

        //是不是有环
        bool flag = false;
        // 因为本题的节点号是从0开始的
        for (int i = 0; i < n; i++) { //枚举每个顶点，注意顶点号从0开始，至n-1止。
            if (!color[i]) {
                flag = dfs(i); //如果当前节点的颜色标识是0,表示还没有访问过，需要继续深搜，
                if (flag) break;
            }
        }

        !flag ? puts("YES") : puts("NO");
    }
    return 0;
}