图的遍历

判断有向图是否成环

用深度优先遍历，为了区分“汇聚点”和“真正的环”，需要给节点打上三种不同的状态：

1. 白色 (0 / Unvisited)：
   • 定义：还没摸过的节点。
2. 灰色 (1 / Visiting)：
   • 定义：节点已经进入递归栈，但它的子孙节点还没有处理完。
3. 黑色 (2 / Visited)：
   • 定义：该节点及其所有子孙节点都已经扫描完毕，退出了递归。

EG:假设有图：$1\to 2,2\to 3,3\to 1$

1. 开始：所有点都是白色。
2. 访问 1：$1$ 变灰色，进入递归栈。
3. 访问 2：从 $1$ 发现 $2$，$2$ 变灰色，进入递归栈。
4. 访问 3：从 $2$ 发现 $3$，$3$ 变灰色，进入递归栈。
5. 回溯检查：从 $3$ 发现 $1$。

// 全局状态数组，初始化为 0 (白色)
int state[MAX_V]; 
 
bool hasCycle(int u, Graph G) {
    // 1. 进入函数，立即将当前节点染成灰色 (正在处理)
    state[u] = 1;
 
    // 2. 遍历当前节点 u 的所有邻接点 v
    for (int v : G.adj[u]) {
        // 如果邻接点是灰色，说明 v 已经在递归栈中，现在 u 又指向 v，形成环！
        if (state[v] == 1) {
            return true; 
        }
        
        // 如果邻接点是白色，递归进入该点
        if (state[v] == 0) {
            if (hasCycle(v, G)) return true;
        }
        
        // 注意：如果 state[v] 是 2 (黑色)，说明该点已处理完且无环，直接跳过
    }
 
    // 3. 离开函数前（即回溯时），将当前节点染成黑色 (彻底处理完)
    state[u] = 2;
    return false;
}