课程表 II / Course Schedule II

怎样从“numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] 返回任一合法课程顺序如 [0,1,2,3] 或 [0,2,1,3]；反例 [[1,0],[0,1]] 有环返回 []。”推导出 拓扑 · 返回课程顺序，并证明每次状态变化都不会漏掉答案？

中心结论：Kahn 拓扑排序：建图 prerequisite→course，统计入度，入度 0 的课入队，每次弹出加入 order 数组，减少后继课程入度，入度变 0 再入队。最后 order.length==numCourses 返回 order，否则返回 []。

现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]。给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

在本站主例中，numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] 返回任一合法课程顺序如 [0,1,2,3] 或 [0,2,1,3]；反例 [[1,0],[0,1]] 有环返回 []。

算法最终需要得到或观察：成功返回任一合法拓扑序 [0,1,2,3] 或 [0,2,1,3]；有环返回空数组 []。

重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
2. 2状态只维护 依赖图 (邻接表)、indegree 入度表、queue 队列、order 最终课程顺序四区同步。
3. 3转移每一步按照 Kahn 拓扑排序：建图 prerequisite→course，统计入度，入度 0 的课入队，每次弹出加入 order 数组，减少后继课程入度，入度变 0 再入队。最后 order.length==numCourses 返回 order，否则返回 []。
4. 4收尾读取 成功返回任一合法拓扑序 [0,1,2,3] 或 [0,2,1,3]；有环返回空数组 []。，并复核边界与复杂度。

先把题目对象翻译成节点和边，再选择 BFS 或 DFS。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：依赖图 (邻接表)、indegree 入度表、queue 队列、order 最终课程顺序四区同步。

给出 n 个任务，每两个任务之间有相互依赖关系，比如 A 任务一定要在 B 任务之前完成才行。问是否可以完成所有任务，如果可以完成任务，就输出完成任务的顺序，如果不能完成，输出空数组。 这一题是第 207 题的加强版。解题思路是 AOV 网的拓扑排序。最后输出数组即可。代码和第 207 题基本不变。具体解题思路见第 207 题。

Kahn 拓扑排序：建图 prerequisite→course，统计入度，入度 0 的课入队，每次弹出加入 order 数组，减少后继课程入度，入度变 0 再入队。最后 order.length==numCourses 返回 order，否则返回 []。

执行过程中持续维护：依赖图 (邻接表)、indegree 入度表、queue 队列、order 最终课程顺序四区同步。

正确性依赖以下不变量：prerequisites[i]=[course,prerequisite] → 边 prerequisite→course；入度 0 的课可修；order.length==numCourses 判断是否有环；拓扑序不唯一。V 是课程数量，E 是依赖关系数量。

面试时可以压缩为：用 Kahn 拓扑排序返回课程顺序。建图时 prerequisite→course，统计入度，把入度 0 的课入队。每次弹出课程加入 order 结果数组，减少后继课程入度，入度变 0 再入队。最后检查 order.length 是否等于 numCourses：相等返回 order，不等说明有环返回空数组。时间 O(V + E)，空间 O(V + E)，V 是课程数量，E 是依赖关系数量。

落到当前题，执行机制可以压缩为：Kahn 拓扑排序：建图 prerequisite→course，统计入度，入度 0 的课入队，每次弹出加入 order 数组，减少后继课程入度，入度变 0 再入队。最后 order.length==numCourses 返回 order，否则返回 []。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] 返回任一合法课程顺序如 [0,1,2,3] 或 [0,2,1,3]；反例 [[1,0],[0,1]] 有环返回 []。 因为：Kahn 拓扑排序：建图 prerequisite→course，统计入度，入度 0 的课入队，每次弹出加入 order 数组，减少后继课程入度，入度变 0 再入队。最后 order.length==numCourses 返回 order，否则返回 []。
2. 2理解边的方向：[course, prerequisite]明确依赖关系的方向。 因为：正确建图是拓扑排序的基础。
3. 3生成邻接表和入度表遍历 prerequisites 建立邻接表和入度数组。 因为：邻接表存储后继课程，入度表记录前置课程数量。
4. 4Step 5: pop 0，加入 order弹出课程 0 并加入 order 数组。 因为：按拓扑序收集课程。
5. 5删除 0 的出边，更新后继入度课程 0 的后继课程入度减 1，入度变 0 则入队。 因为：解锁依赖该课程的后续课程。
6. 6预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
7. 7删除 1 的出边，更新后继入度课程 1 的后继课程入度减 1，入度变 0 则入队。 因为：解锁依赖该课程的后续课程。
8. 8收尾与复杂度成功返回任一合法拓扑序 [0,1,2,3] 或 [0,2,1,3]；有环返回空数组 []。 因为：时间 O(V + E) · 空间 O(V + E)。Kahn 拓扑排序：建图 prerequisite→course，统计入度，入度 0 的课入队，每次弹出加入 order 数组，减少后继课程入度，入度变 0 再入队。最后 order.length==numCourses 返回 order，否则返回 []。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func findOrder(numCourses int, prerequisites [][]int) []int {
	in := make([]int, numCourses)
	frees := make([][]int, numCourses)
	next := make([]int, 0, numCourses)
	for _, v := range prerequisites {
		in[v[0]]++
		frees[v[1]] = append(frees[v[1]], v[0])
	}
	for i := 0; i < numCourses; i++ {
		if in[i] == 0 {
			next = append(next, i)
		}
	}
	for i := 0; i != len(next); i++ {
		c := next[i]
		v := frees[c]
		for _, vv := range v {
			in[vv]--
			if in[vv] == 0 {
				next = append(next, vv)
			}
		}
	}
	if len(next) == numCourses {
		return next
	}
	return []int{}
}

func main() {
    // 1. 主例
    //    输入：mode="course-schedule", numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
    //    期望：成功返回任一合法拓扑序 [0,1,2,3] 或 [0,2,1,3]；有环返回空数组 []。
    //
    // 2. 失败 / 未命中
    //    检查：边方向写反 (应该是 prerequisite→course)；以为拓扑序唯一；忘记检查 order.length==numCourses；把 Kahn BFS 当成普通 BFS；只返回 true/false 而不是 order 数组。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC207 课程表 (判断能否完成)；LC269 火星词典；LC310 最小高度树
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] 返回任一合法课程顺序如 [0,1,2,3] 或 [0,2,1,3]；反例 [[1,0],[0,1]] 有环返回 []。
2. 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
3. 3优化Kahn 拓扑排序：建图 prerequisite→course，统计入度，入度 0 的课入队，每次弹出加入 order 数组，减少后继课程入度，入度变 0 再入队。最后 order.length==numCourses 返回 order，否则返回 []。
4. 4证明prerequisites[i]=[course,prerequisite] → 边 prerequisite→course；入度 0 的课可修；order.length==numCourses 判断是否有环；拓扑序不唯一。V 是课程数量，E 是依赖关系数量。
5. 5复杂度时间 O(V + E)，空间 O(V + E)