210 课程表 II

题目描述#

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites，其中 prerequisites[i] = [ai, bi] 表示在选修课程 ai 前必须先选修 bi。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，只要返回任意一种即可。如果不可能完成所有课程，返回空数组。

思路#

在 207 课程表的基础上，不仅要判断能否完成，还要给出一个具体的拓扑排序。

依然使用三色标记法做 DFS：0 未访问、1 访问中、2 已完成。关键观察是：当一个节点被染成 2（即它所有后继都已处理完毕）时，把它加入结果数组，最后反转，就是一个合法的拓扑序。

原因：节点被标为 2 的时刻，意味着它指向的所有课程都已经先被标为 2 并加入了数组。因此数组中越靠前的节点，越是"后继"；反转之后，前置课程自然排在后继课程之前。

如果过程中发现环（遇到颜色为 1 的邻居），直接返回空数组。

知识边界#

DFS 拓扑排序的核心思想：后序遍历 + 反转。这是因为 DFS 离开一个节点（染为 2）时，它依赖的所有节点都已经完成，所以后序序列反转即为拓扑序
相比 BFS（Kahn 算法）维护入度队列的写法，DFS 版本天然在环检测与拓扑排序之间共享代码，成本只是多一个结果数组和一次反转
反转可以用头尾双指针原地完成，避免额外的空间开销

代码#

func findOrder(numCourses int, prerequisites [][]int) []int {
    graph := make([][]int, numCourses)
    for _, p := range prerequisites {
        graph[p[1]] = append(graph[p[1]], p[0])
    }
    colors := make([]int, numCourses)

    // 我们用一个result数组保存结果
    result := make([]int, 0, 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
        result = append(result, x)
        return false // 没有找到环
    }

    for i, x := range colors {
        if x == 0 && dfs(i) {
            return []int{}
        }
    }
    for l, r := 0, len(result)-1; l < r; l, r = l+1, r-1 {
        result[l], result[r] = result[r], result[l]
    }
    return result
}