《Circle Detect》题目分析

这道题是一道经典图论题，判断有向图中是否有环。

比较常用的做法是DFS，同时在DFS过程中对点染色：

1. 还没被DFS访问的点是白色的，初始时所有点都是白色的
2. 如果点u已经被DFS访问过，但是u的子节点还未全部被访问到，那么把u染成灰色
3. 如果点u以及u的子节点都被访问过了，从u回溯到u的父节点时，将u染成黑色

如果在DFS的过程中我们沿着有向边到达了一个灰色节点，则说明图中有环；如果从未到达过灰色节点，说明没有环。

伪代码如下：

DFS(x):
    color[x] = GREY
    FOR y : g[x] # x->y是一条边
        IF color[y] == GREY
            EXIT(CIRCLE_FOUND)
        IF color[y] == WHITE
            DFS(y)
    color[x] = BLACK
MAIN:
    FOR x = 1 .. N:
        IF color[x] == WHITE:
            DFS(x)
    EXIT(CIRCLE_NOT_FOUND)