207 课程表

题目描述#

共有 numCourses 门课程（编号 0 到 numCourses - 1），部分课程有先修要求：prerequisites[i] = [ai, bi] 表示学 ai 之前必须先学 bi。判断是否能完成所有课程的学习。

思路#

把课程之间的先修关系建成有向图：bi → ai 表示 bi 是 ai 的前置。问题等价于这张有向图中是否存在环——有环则无法完成，无环则可以。

用 DFS 做拓扑排序的环检测。给每个节点标记三种颜色：0 未访问、1 访问中（在当前递归栈上）、2 已完成。从每个未访问节点出发做 DFS，进入节点时染为 1，离开时染为 2。如果在 DFS 过程中遇到颜色为 1 的邻居，说明走回了当前路径上的某个节点，即发现了环。颜色为 2 的节点已经确认无环，直接跳过。

最终遍历所有节点，只要有一次 DFS 返回"发现环"，整体返回 false；全部通过则返回 true。

知识边界#

三色标记法（白/灰/黑，即 0/1/2）是有向图环检测的经典手法，区别于无向图用简单 visited 数组的做法；颜色 1 代表"在递归栈中"，这是发现有向环的关键
颜色 2 的剪枝很重要：已完成的节点无论如何都不会构成新的环，跳过可以避免重复遍历，将复杂度控制在 O(V+E)
建图时方向是 bi → ai（前置指向后继），和题目描述的 [ai, bi] 顺序相反，容易写错

代码#

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make([][]int, numCourses)
    for _, p := range prerequisites {
        graph[p[1]] = append(graph[p[1]], p[0])
    }
    colors := make([]int, numCourses)
    // 当dfs返回true的时候说明找到了环
    var dfs func(int) bool
    dfs = func(x int) bool {
        // 标记x正在访问中
        colors[x] = 1
        for _, y := range graph[x] {
            // 情况一：colors[y] == 1，表示发生循环依赖，找到了环
            // 情况二：colors[y] == 0，没有访问过 y，继续递归 y 获取信息
            // 情况三：colors[y] == 2，重复访问 y 只会重蹈覆辙，和之前一样无法找到环，跳过
            if colors[y] == 1 || (colors[y] == 0 && dfs(y)) {
                return true // 找到了环
            }
        }
        // 这时候x已经访问完毕，可以理解为从x出发无法找到环
        colors[x] = 2
        return false // 没有找到环
    }

    for i, c := range colors {
        if c == 0 && dfs(i) {
            return false
        }
    }
    return true
}