课程表

怎样从“numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] 能否修完；反例 [[1,0],[2,1],[0,2]] 有环。”推导出 拓扑 · Kahn 判环，并证明每次状态变化都不会漏掉答案？

中心结论：建图+入度+Kahn 队列；processed==numCourses 则无环。

现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]。给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

在本站主例中，numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] 能否修完；反例 [[1,0],[2,1],[0,2]] 有环。

算法最终需要得到或观察：正例 true；反例 false。

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

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

1. 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
2. 2状态只维护 依赖图、indegree 表、queue、processed 四区同步。
3. 3转移每一步按照 建图+入度+Kahn 队列；processed==numCourses 则无环。
4. 4收尾读取 正例 true；反例 false。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：依赖图、indegree 表、queue、processed 四区同步。

给出 n 个任务，每两个任务之间有相互依赖关系，比如 A 任务一定要在 B 任务之前完成才行。问是否可以完成所有任务。 这一题就是标准的 AOV 网的拓扑排序问题。拓扑排序问题的解决办法是主要是循环执行以下两步，直到不存在入度为0的顶点为止。 1. 选择一个入度为0的顶点并输出之； 2. 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，即无法完成所有任务；否则输出的顶点序列就是一种拓扑序列，即可以完成所有任务。

建图+入度+Kahn 队列；processed==numCourses 则无环。

执行过程中持续维护：依赖图、indegree 表、queue、processed 四区同步。

正确性依赖以下不变量：prerequisites[i]=[a,b] → 边 b→a；indegree 0 的课可修；processed==numCourses 判无环。

面试时可以压缩为：有向图 + Kahn：入度 0 入队，修完减后继入度，processed==numCourses 判环。

落到当前题，执行机制可以压缩为：建图+入度+Kahn 队列；processed==numCourses 则无环。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

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

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

// AOV 网的拓扑排序
func canFinish(n int, pre [][]int) bool {
	in := make([]int, n)
	frees := make([][]int, n)
	next := make([]int, 0, n)
	for _, v := range pre {
		in[v[0]]++
		frees[v[1]] = append(frees[v[1]], v[0])
	}
	for i := 0; i < n; 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)
			}
		}
	}
	return len(next) == n
}

func main() {
    // 1. 主例
    //    输入：mode="course-schedule", numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
    //    期望：正例 true；反例 false。
    //
    // 2. 失败 / 未命中
    //    检查：边画反；只看 queue 空；复杂度误写 O(n)/O(1)；忽略多个入度 0。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC210 课表 II；LC802 事件
}

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

1. 1题意numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] 能否修完；反例 [[1,0],[2,1],[0,2]] 有环。
2. 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
3. 3优化建图+入度+Kahn 队列；processed==numCourses 则无环。
4. 4证明prerequisites[i]=[a,b] → 边 b→a；indegree 0 的课可修；processed==numCourses 判无环。
5. 5复杂度时间 O(V+E)，空间 O(V+E)