判断图中是否有环

一、无向图

DFS

访问过的节点标记，如果遇到已访问且不是父节点，就是环。

boolean dfs(int node, int parent) {
    visited[node] = true;
    for (int next : adj[node]) {
        if (!visited[next]) {
            if (dfs(next, node)) return true;
        } else if (next != parent) {
            return true;
        }
    }
    return false;
}

并查集

边的两个点，如果已连通，加这条边就成环。

二、有向图

DFS 三色标记

• 白：未访问。
• 灰：访问中。
• 黑：访问完。

遇到灰色就是环。

boolean dfs(int node) {
    color[node] = 1; // 灰
    for (int next : adj[node]) {
        if (color[next] == 1) return true; // 环
        if (color[next] == 0 && dfs(next)) return true;
    }
    color[node] = 2; // 黑
    return false;
}

拓扑排序

能排完就无环，排不完就有环。

三、复杂度

O(V+E)。

一句话

无向图用 DFS/并查集，有向图用三色标记/拓扑排序。