210. 课程表 II（Course Schedule II）
难度：中等 | 主题：图论、拓扑排序、BFS、DFS
题目
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses-1。在选修某些课程之前需要一些先修课程。给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
示例
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,1,2,3] 或 [0,2,1,3]
思路
先讲个故事：选课系统的最优顺序
教务系统不仅要知道能不能选完，还要给出最优选课顺序。
Kahn 算法天然就能输出拓扑序——每次处理入度为 0 的节点时，就把它加入结果列表。
引导式推导：207 的一行升级
与 207 题的关系： 207 只判断是否有环，210 还要输出拓扑序。
flowchart TD A["建图 + 入度数组"] --> B["入度为 0 的入队"] B --> C["出队 → 加入 result"] C --> D["后继入度 -1"] D --> E{"入度变 0?"} E -->|"是"| F["入队"] E -->|"否"| G["继续"] F --> H{"队列空?"} G --> H H -->|"否"| C H -->|"是"| I["result 长度 == numCourses?"] I -->|"是"| J["返回 result"] I -->|"否"| K["有环 → 返回 []"]
关键洞察： BFS 拓扑排序（Kahn 算法）天然可以输出拓扑序——每次处理入度为 0 的节点时，就把它加入结果列表。
代码
from collections import deque, defaultdict
class Solution:
def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
graph = defaultdict(list)
indegree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indegree[a] += 1
queue = deque()
for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)
result = []
while queue:
course = queue.popleft()
result.append(course)
for next_course in graph[course]:
indegree[next_course] -= 1
if indegree[next_course] == 0:
queue.append(next_course)
return result if len(result) == numCourses else []
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(V+E) | 建图 + 拓扑排序 |
| 空间 | O(V+E) | 图 + 入度数组 + 结果 |
实战考量
频率分析
出现在：字节/阿里 高频题，约 30% 常会考到。207 的进阶版，考察拓扑序输出。
延伸思考
Q：拓扑序唯一吗？
A：不唯一，入度为 0 的节点可能有多个，选哪个都行。
Q：怎么保证输出字典序最小的拓扑序？
A：用最小堆（优先队列）代替普通队列，每次选编号最小的。
Q：如果要求并行上课（每学期尽可能多的课）呢？
A：按层输出拓扑序，每层是可以同时上的课。
Q：如果要求输出所有可能的拓扑序呢？
A：DFS + 回溯，每次选一个入度为 0 的节点，递归处理。
易错点
-
最后检查
len(result) == numCourses -
有环时返回空列表不是 None
-
拓扑序不唯一，题目只要求返回任意一个
生活类比
选课系统的最优顺序
教务系统不仅想知道能不能选完，还要给出一个选课清单。
Kahn 算法每次选一门没有先修要求的课（入度为 0），加入清单。
选完后，依赖它的课的先修数 -1，如果变成 0 就可以选了。
最后清单就是拓扑序——按这个顺序选课，保证先修课在前面。
入度为 0 = 可以选 = 加入清单——这就是拓扑排序输出顺序。
相关题目
| 题目 | 关系 |
|---|---|
| 207课程表 | 只判环，不输出顺序 |
| 210课程表II | 本题 |
| 684冗余连接 | 无向图判环 |
→ 返回题单：LeetCode学习路线图 > 十二、图论
速记卡（面试闪卡）
Q1：一句话讲清「210. 课程表 II（Course Schedule II）」到底是什么？
A：给定先修关系，输出能学完所有课程的拓扑顺序。
Q2：思路 —— 怎么理解？
A：像教务排课：每次选一门没有先修要求的课（入度为 0）加入清单，它解放的后继先修数 -1。这就是 Topological Sort（拓扑排序）/ Kahn 算法。
Q3：代码 —— 怎么理解？
A：建图+入度数组，入度 0 入队；出队加入 result，后继入度 -1，变 0 再入队。最后 result 长度==numCourses 才有效，否则有环返 []。
Q4：复杂度 —— 怎么理解？
A：时间 O(V+E)（建图+排序），空间 O(V+E)（图+入度+结果）。BFS 天然输出拓扑序。
Q5：实战考量 —— 怎么理解？
A：字节/阿里高频，207 的进阶（207 只判环）。拓扑序不唯一；要字典序最小用最小堆；有环返 [] 不是 None。
Q6：核心速记主线有哪些？
-
Kahn 算法：入度 0 入队，处理完后继入度 -1
-
BFS 天然输出拓扑序，每次出队加入结果
-
时间 O(V+E)、空间 O(V+E)
-
易错：检查 len==numCourses，有环返 [] 非 None
口诀
A：选课排顺序
入度零先去
后继减一数
拓扑序清晰