LeetCode 210. 课程表 II
目录
题目描述
题意分析
有编号
0到numCourses - 1的若干门课，prerequisites[i] = [a, b]表示想学a就必须先学完b。要求返回一种能学完全部课程的学习顺序；如果根本学不完，返回空数组。答案不唯一，只要满足所有先修约束即可。这里和「课程表 I」的差别要先摆清楚：I 只问能不能学完，返回布尔值；II 要求把顺序本身交出来。也就是说，判定环的能力仍然需要，但还要在判定过程中把一条合法序列记录下来。
约束透露的信号有几层。课程用连续整数编号，说明所有的「表」都可以用数组而不是哈希；课程数最多两千、先修关系数量上限约为课程数的平方，说明 $O(n + m)$ 或 $O(n \log n)$ 级别都能过，但枚举顺序的指数级做法一定不行；题目没有承诺图是连通的，也没有承诺先修关系不重复。
边界有四类：
prerequisites为空时任意顺序都合法；只有一门课时直接返回[0]；出现形如[a, a]的自我依赖时必然无解；多个互不相连的分量要一起输出，不能只走出发点所在的那一块。
解法：BFS 拓扑排序
核心思路
问题关键：
[course, pre]是一条先后约束，应建成有向边pre -> course。一门课能进入结果的充要条件是它所有先修课都已完成，也就是剩余入度为0。为什么选 Kahn 算法：如果每轮重扫全部课程来找可学课程，会反复检查没有变化的节点。入度法只在学完一门课时更新它的直接后继，使每个点和每条边都只处理一次；同时，出队顺序就是所求拓扑序，无需再做一次判环。
不变量：
indegree[x]始终等于课程x尚未完成的先修课数量；队列中都是尚未输出且入度为0的课程；order中每门课的先修课都已排在它前面。正确性：每次只把入度为
0的课程加入order，因此不会违反任何先修约束。移除它的出边后，后继入度减到0当且仅当其先修课已全部完成，所以所有可继续学习的课程都会被发现。若最终输出n门课，所得顺序合法；若不足n，剩余子图没有零入度点，沿前驱不断回溯必然形成环，因此不存在合法顺序。
解题步骤
- 按
pre -> course建邻接表，并统计每门课的入度。- 将所有零入度课程入队，不能只选一个，否则会漏掉独立分量。
- 依次出队写入答案；遍历其后继并将入度减一，刚好减到
0时入队。- 结束后若答案长度为
numCourses就返回，否则返回空数组。口述样例：
[[1,0],[2,0],[3,1],[3,2]]的初始入度是[0,1,1,2]。先输出0，释放1、2；两者都输出后才把3的入度降到0，可得到[0,1,2,3]。边界检查：无依赖时所有课程一开始都入队；自环
[0,0]或互相依赖[[1,0],[0,1]]都无法完整出队，最终返回空数组。
代码实现
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
int[] indegree = new int[numCourses];
for (int[] edge : prerequisites) {
graph.get(edge[1]).add(edge[0]);
indegree[edge[0]]++;
}
Queue<Integer> queue = new ArrayDeque<>();
for (int course = 0; course < numCourses; course++) {
if (indegree[course] == 0) {
queue.offer(course);
}
}
int[] order = new int[numCourses];
int idx = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
order[idx++] = course;
for (int next : graph.get(course)) {
if (--indegree[next] == 0) {
queue.offer(next);
}
}
}
return idx == numCourses ? order : new int[0];
}
}
func findOrder(numCourses int, prerequisites [][]int) []int {
graph := make([][]int, numCourses)
indegree := make([]int, numCourses)
for _, edge := range prerequisites {
course := edge[0]
pre := edge[1]
graph[pre] = append(graph[pre], course)
indegree[course]++
}
queue := make([]int, 0)
for course := 0; course < numCourses; course++ {
if indegree[course] == 0 {
queue = append(queue, course)
}
}
order := make([]int, 0, numCourses)
for head := 0; head < len(queue); head++ {
course := queue[head]
order = append(order, course)
for _, next := range graph[course] {
indegree[next]--
if indegree[next] == 0 {
queue = append(queue, next)
}
}
}
if len(order) != numCourses {
return []int{}
}
return order
}
复杂度分析
- 时间复杂度：$O(n+m)$，
n为课程数，m为依赖数；每个点至多入队一次，每条边至多处理一次。- 空间复杂度：$O(n+m)$，邻接表占 $O(m)$，入度、队列和结果占 $O(n)$。
关键点总结
- 建边方向决定答案方向：先修课指向后续课程。
- 判环不看边数，只看最终是否输出全部节点。
- 答案不唯一；若要求字典序最小，将普通队列换成小根堆，复杂度变为 $O(m+n\log n)$。
- DFS 三色标记也能拓扑排序，但需要逆序结果；本题用入度法更直观。
易错点总结
- 把边建成
course -> pre：[[1,0]]会错误输出[1,0]。- 只把一个零入度点入队：存在多个独立分量时会漏课。
- 后继入度减一后无条件入队：课程可能在其他先修课尚未完成时被输出。
- 不比较最终输出数量：有环时会把不完整序列误当答案。
- 测试时认定拓扑序唯一：同一张图可能有多种合法结果，应检查约束而非固定数组。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 207. 课程表 | 中等 | 同一套入度法，但只需返回能否学完，不必记录出队顺序 |
| 269. 火星词典 | 困难 | 难点在从相邻单词的首个差异字符推出边，建图本身就是主要工作量 |
| 310. 最小高度树 | 中等 | 无向图上按度为 1 逐层剥叶子，是入度法在树上的对称变形 |
| 444. 序列重建 | 中等 | 要求拓扑序唯一，判定条件变成队列中始终最多只有一个元素 |
| 630. 课程表 III | 困难 | 与依赖无关，是按截止时间排序加大根堆反悔的贪心 |
| 1462. 课程表 IV | 中等 | 回答任意两点的可达性查询，需要传递闭包或在拓扑过程中传播祖先集 |
| LCR 113. 课程表 II | 中等 | 本题的 LCR 版本，输入输出完全一致，可用来复核实现 |
| LCR 114. 火星词典 | 困难 | 269 的 LCR 版本，同样要处理前缀更长的非法输入 |
| LCR 115. 序列重建 | 中等 | 444 的 LCR 版本，判定唯一性的写法一致 |
| 面试题 04.01. 节点间通路 | 中等 | 只判断有向图中两点是否可达，用搜索即可，不需要排出全序 |