环的判断.md

拓扑 / 统计度

1. 求出所有结点的度。（无向图不区分入度和出度）

2. 将所有入度为0的结点入队。(可视为根节点)

3. 循环弹出队首元素，把与队首元素相邻节点的入度减1。如果相邻节点的入度变为0，则将其入队。

4. 如果存在元素未入队，则说明有环。

   1
   |
   2
 /   \
3 --- 4

以上图为例，循环结束后，2, 3, 4 的入度为 2，不满足进队列的条件而被剩下，说明有环。

DFS

1. 遍历每个点，以每个点为起点，进行 DFS。如果起点之前被访问过了，则跳过
2. DFS 期间如果有节点在本轮遍历中被访问过了，说明有环
3. 可以用三色标记法实现：

func dfs(node int, children [][]int, colors []int) bool {
    color[node] = Grey  // dfs开始时将访问的点标记为灰色，结束时标记为黑色，后续如果再次读到灰色的点说明有环
    for _, child := range children[node] {
        if (color[child] == Grey) { return true } // 读到灰色的点，说明有环
        if (color[child] == White && dfs(child, children, colors)) { return true }
    }
    color[node] = Black // dfs结束时标记为黑色
}

为啥需要黑色节点？因为如果只用两个颜色，如下情况中的3会被误判：

1   2
 \ /
  3

并查集

其实思路和 DFS 差不多。

1. 遍历每个起点 i，对其 DFS 。把 DFS 到的子节点的 parent 指向 i。
2. DFS 别的起点时，如果有的子节点已经有 parent 了，说明存在环

Samples

207. Course Schedule
208. Course Schedule II
209. Find Eventual Safe States