# 环的判断

## 拓扑 / 统计度

1. 求出所有结点的度。（无向图不区分入度和出度）
2. 将所有入度为0的结点入队。(可视为根节点)
3. 循环弹出队首元素，把与队首元素相邻节点的入度减1。如果相邻节点的入度变为0，则将其入队。
4. 如果存在元素未入队，则说明有环。

```
   1
   |
   2
 /   \
3 --- 4
```

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

## DFS

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

```go
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