课程表 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

题意

给你一个有向图，判断图中是否有环。

核心思路

如果在递归过程中，发现下一个节点在递归栈中（正在访问中），则找到了环。

如上图，我们 DFS 访问 $0 \to 3 \to 4 \to 5 \to 3$ 。走到 $5$ 的时候，发现下一个节点 $3$ 在递归栈中（正在访问中），那么就找到了环。

注：说节点 $x$ 「正在访问中」，是说我们正在递归处理节点 $x$ 的邻居， $dfs (x)$ 尚未结束。

具体思路

对于每个节点 $x$ ，都定义三种颜色值（状态值）：

$0$ ：节点 $x$ 尚未被访问到。 $1$ ：节点 $x$ 正在访问中， $dfs (x)$ 尚未结束。 $2$ ：节点 $x$ 已经完全访问完毕。注意这还说明从 $x$ 出发无法找到环。所以当我们遇到状态值为 $2$ 的节点 $x$ 时，无需递归 $x$ 。

⚠误区：不能只用两种状态表示节点「没有访问过」和「访问过」。如上图，我们先 DFS 访问 $0 \to 1 \to 2$ ，再访问 $0 \to 2$ ，此时 $0$ 的邻居 $2$ 已经访问过，但这并不能表示此时就找到了环。

算法流程：

建图：把每个 $prerequisites [i] = [a, b]$ 看成一条有向边 $b \to a$ ，构建一个有向图 $g$ 。
创建长为 $numCourses$ 的颜色数组 $colors$ ，所有元素值初始化成 $0$ 。
遍历 $colors$ ，如果 $colors [i] = 0$ ，则调用递归函数 $dfs (i)$ 。
执行 $dfs (x)$ ：
1. 首先标记 $colors [x] = 1$ ，表示节点 $x$ 正在访问中。
2. 然后遍历 $x$ 的邻居 $y$ 。如果 $colors [y] = 1$ ，则找到环，返回 $true$ 。如果 $colors [y] = 0$ （没有访问过）且 $dfs (y)$ 返回了 $true$ ，那么 $dfs (x)$ 也返回 $true$ 。
3. 如果没有找到环，那么先标记 $colors [x] = 2$ ，表示 $x$ 已经完全访问完毕，然后返回 $false$ 。
如果 $dfs (i)$ 返回 $true$ ，那么找到了环，返回 $false$ 。
如果遍历完所有节点也没有找到环，返回 $true$ 。

Python 解法1C++ 解法1

python

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        g = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            g[b].append(a)

        colors = [0] * numCourses
        # 返回 True 表示找到了环
        def dfs(x: int) -> bool:
            colors[x] = 1  # x 正在访问中
            for y in g[x]:
                # 情况一：colors[y] == 1，表示发生循环依赖，找到了环
                # 情况二：colors[y] == 0，没有访问过 y，继续递归 y 获取信息
                # 情况三：colors[y] == 2，重复访问 y 只会重蹈覆辙，和之前一样无法找到环，跳过
                if colors[y] == 1 or colors[y] == 0 and dfs(y):
                    return True  # 找到了环
            colors[x] = 2  # x 完全访问完毕，从 x 出发无法找到环
            return False  # 没有找到环

        for i, c in enumerate(colors):
            if c == 0 and dfs(i):
                return False  # 有环
        return True  # 没有环

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(numCourses);
        for (auto& p : prerequisites) {
            g[p[1]].push_back(p[0]);
        }

        vector<int> colors(numCourses);
        // 返回 true 表示找到了环
        auto dfs = [&](this auto&& dfs, int x) -> bool {
            colors[x] = 1; // x 正在访问中
            for (int y : g[x]) {
                // 情况一：colors[y] == 1，表示发生循环依赖，找到了环
                // 情况二：colors[y] == 0，没有访问过 y，继续递归 y 获取信息
                // 情况三：colors[y] == 2，重复访问 y 只会重蹈覆辙，和之前一样无法找到环，跳过
                if (colors[y] == 1 || colors[y] == 0 && dfs(y)) {
                    return true; // 找到了环
                }
            }
            colors[x] = 2; // x 完全访问完毕，从 x 出发无法找到环
            return false; // 没有找到环
        };

        for (int i = 0; i < numCourses; i++) {
            if (colors[i] == 0 && dfs(i)) {
                return false; // 有环
            }
        }
        return true; // 没有环
    }
};