LeetCode LCR 113. 课程表 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 拓扑排序
核心思路
最朴素的想法是枚举全部
n!种学习顺序，逐个检查是否违反先修约束，显然不可行。稍微聪明一点的做法是每一轮扫描所有还没学的课程，找出「先修课都学完了」的那些学掉，这样虽然正确，但每轮都要重扫全部课程和全部边，最坏是 $O(n \cdot m)$。瓶颈很清楚：一门课的可学状态只会因为「它的某个先修课刚被学完」而改变，全量重扫做了大量无效检查。关键观察是把先修关系画成有向边
b -> a（先修课指向后续课），那么「课程a现在可学」等价于「a在图中所有指向它的边的起点都已被学完」，也就是等价于「a的剩余入度为0」。于是完全不必重扫：每学完一门课，只需沿着它的出边把后继课程的剩余入度各减一，恰好只有减到0的那些课变成新的可学课程，其余状态不受影响。这把每轮全扫压成了「每条边只被处理一次」。由此得到贯穿全程的不变量：在任何时刻，
indegree[x]恰好等于「课程x的先修课中尚未写入结果序列的数量」，而结果序列order中的每一门课，其所有先修课都已经排在它前面。初始化时结果序列为空，indegree[x]就是x的原始入度，不变量成立；每次从队列取出一门入度为0的课写入序列，它的每个后继的未完成先修数正好少一个，所以对应减一，不变量继续保持。终止情况也由不变量直接推出：队列空意味着所有未写入的课程剩余入度都大于等于
1，即每个点都还有一个未完成的先修课。在有限点集里，沿着「未完成先修」一直往回走必然重复访问某个点，也就是必然存在环，所以此时无解。反过来，如果写入数量等于课程总数，序列本身就是一个合法的学习顺序。判环和产序在这里是同一次遍历的两个副产品，这正是本题相对课程表 I 只需多一个order数组的原因。
解题步骤
- 建邻接表
graph和入度数组indegree。对每条[a, b]执行graph[b].add(a)与indegree[a]++，方向必须是先修课指向后续课，因为后面要「学完一门课去释放它的后继」。- 扫描所有课程，把入度为
0的全部入队。这些课没有任何先修要求，是唯一能作为起点的候选；必须一次全放进去，否则会漏掉不连通的分量。- 循环取出队首课程，写入结果数组并让下标前移。出队顺序就是学习顺序，这一步是本题与只判环的版本唯一的实质差别。
- 遍历该课程的所有后继，各自入度减一；只有减到
0的才入队。减不到0说明它还有别的先修课没学，现在入队会破坏顺序合法性。- 循环结束后比较写入数量与课程总数：相等则返回结果数组，否则说明剩余课程互相成环，返回空数组。
以
numCourses = 4、prerequisites = [[1,0],[2,0],[3,1],[3,2]]走一遍：建图后graph[0] = [1,2]、graph[1] = [3]、graph[2] = [3]、graph[3] = []，入度为indegree = [0,1,1,2]。初始化时只有课程0入度为0，队列为[0]，order = []。第一轮取出0，order = [0]；遍历后继1，入度由1减到0，入队；遍历后继2，入度由1减到0，入队；此时队列为[1,2]，indegree = [0,0,0,2]。第二轮取出1，order = [0,1]；后继3的入度由2减到1，未到0不入队。第三轮取出2，order = [0,1,2]；后继3的入度由1减到0，入队。第四轮取出3，order = [0,1,2,3]，它没有后继。队列空，写入数量4等于课程总数，返回[0,1,2,3]。若把[1,0]改成[0,3]，则0的入度变为1，四门课入度全部大于0，初始队列为空，一轮都进不去，写入数量0小于4，返回空数组。
代码实现
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)) {
indegree[next]--;
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)
// 入度降为 0 时，说明该课程的先修课已经全部完成。
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为先修关系数。建图遍历每条边一次，初始化扫描每个点一次；主循环中每个点最多入队出队一次（入度只减不增，减到0仅发生一次），每条边在其起点出队时被处理一次。- 空间复杂度：$O(n + m)$。邻接表存下全部
m条边，入度数组与队列各占 $O(n)$，结果数组同为 $O(n)$。
关键点总结
- 「找一个满足偏序约束的线性顺序」这类问题，通用建模是把约束变成有向边、把「可执行」变成「剩余入度为
0」，任务调度、编译依赖、事件排期都能套这一层抽象。- 增量维护优于全量重扫：状态只在相邻元素变化时才可能改变，就该沿边推送更新，而不是每轮重新判断所有对象。
- 判环与产序可以合并：入度法在同一次遍历里既得到序列，又通过「写入数量是否等于点数」得到有环判定，不需要额外跑一次环检测。
- 初始队列必须放入全部零入度点，这是保证不连通分量都被覆盖的唯一入口。
- 面试视角：本题最常见的追问是「和课程表 I 有什么区别」，标准回答是算法框架完全相同，只是把计数器换成记录出队序列；其次是「BFS 和 DFS 两种拓扑排序怎么选」，可以答 DFS 需要三色标记判环并把结果逆序输出，边界更易写错，而 BFS 的入度法状态直观、天然给出正序，白板上更稳；若追问「要求字典序最小的顺序」，把队列换成小根堆即可，代价是复杂度升到 $O(n \log n + m)$。
易错点总结
- 错误写法：把边建成
graph[a].add(b)，即后续课指向先修课 → 对numCourses = 2、prerequisites = [[1,0]]，入度为0的会变成课程1，输出[1,0]，恰好把先修顺序整个颠倒。- 错误写法：只把「某一个」入度为
0的课程入队就开始循环 → 输入numCourses = 4、prerequisites = [[1,0],[3,2]]时，只放入0会漏掉另一条链的起点2，写入数量小于课程总数，被误判成有环并返回空数组。- 错误写法：后继入度减一后无条件入队 → 该课程会在剩余先修课学完前就被写入序列，且可能被重复写入多次，结果数组越界或顺序非法。
- 错误写法：循环结束后直接返回
order而不比较数量 → 存在环时数组尾部留着未填的默认值0，会返回一串带有重复0的非法序列，而不是要求的空数组。- 错误写法：用「
prerequisites长度是否为0」之类的条件判断有没有环 → 环的存在与边数多少无关，[[0,1],[1,0]]只有两条边却无解。- 错误写法：把 Java 的判环条件写成
queue.isEmpty() && idx < numCourses之外的启发式判断，例如统计剩余入度之和是否为0之后又忘记返回空数组 → 有环用例下仍然返回了部分序列，判定为答案不完整。- 错误写法：邻接表按课程数分配，却用先修关系的下标去索引，或忘记为每门课初始化空列表 → Java 侧访问未初始化的元素抛空指针，Go 侧则会因为切片长度不足而越界。
- 错误写法：假设图连通、只从课程
0出发做一次遍历 → 多个独立分量时只输出了一部分课程，数量校验失败。- 错误写法：认为答案唯一，据此写死某个期望序列去自测 → 本题接受任意合法顺序，用固定字符串比对会把正确实现误判成错误。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 207. 课程表 | 中等 | 同一套入度法，但只需返回能否学完，不必记录出队顺序 |
| 269. 火星词典 | 困难 | 难点在从相邻单词的首个差异字符推出边，建图本身就是主要工作量 |
| 310. 最小高度树 | 中等 | 无向图上按度为 1 逐层剥叶子，是入度法在树上的对称变形 |
| 444. 序列重建 | 中等 | 要求拓扑序唯一，判定条件变成队列中始终最多只有一个元素 |
| 630. 课程表 III | 困难 | 与依赖无关，是按截止时间排序加大根堆反悔的贪心 |
| 1462. 课程表 IV | 中等 | 回答任意两点的可达性查询，需要传递闭包或在拓扑过程中传播祖先集 |
| LCR 114. 火星词典 | 困难 | 269 的 LCR 版本，同样要处理前缀更长的非法输入 |
| LCR 115. 序列重建 | 中等 | 444 的 LCR 版本，判定唯一性的写法一致 |
| 面试题 04.01. 节点间通路 | 中等 | 只判断有向图中两点是否可达，用搜索即可，不需要排出全序 |