题干与适用场景
有 num_courses 门课程，编号为 0 到 num_courses - 1。每个先修关系 [course, prerequisite] 表示必须先学 prerequisite，才能学 course。请返回任意一个能完成 全部课程的顺序；如果不存在这样的顺序，返回空列表。
本题约定 0 <= num_courses <= 2000，课程编号合法，每对关系互不相同，且不存在自己依赖自己 的输入边。num_courses == 0 时返回空列表。对于 num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]， [0, 1, 2, 3] 和 [0, 2, 1, 3] 都正确；对于 [[1, 0], [0, 1]]，两门课互相依赖，只能返回空列表。
这道题适用于通用软件工程编码面试，核心是把自然语言里的依赖转换成有向图，再判断图是否为 有向无环图。基础任务只要求任意合法顺序，不要求字典序最小，也不计算每门课的耗时或并发容量。
面试官考察点
第一项信号是边的方向。[course, prerequisite] 应建立 prerequisite -> course，因为完成先修课后才能释放后续课程。反向建图仍可能跑出一个排列， 但排列表达的是相反约束，无法回答题目。
第二项信号是能否从“当前可以选的课程”推导入度。某门课的入度表示尚未满足的直接先修课数量。 入度为零时才能进入候选队列；完成一门课后，只减少它直接后继的入度。强回答会说清这个状态含义， 而不是只背诵“用 BFS”。
第三项信号是环检测。不能因为队列变空就直接返回已得到的部分顺序。只有结果长度等于课程总数时， 全部节点才被处理；长度不足说明剩余子图没有零入度节点，其中必然存在有向环。
面试官还会检查复杂度、边界和契约意识。邻接表实现需要 O(V + E) 时间和空间；使用 deque.popleft() 能保持队首删除为常数时间。多种合法顺序、互不连通的课程、空输入和长依赖链都 应在测试中出现。
回答前需要澄清的问题
- 返回任意顺序还是字典序最小顺序？ 任意顺序使用普通队列即可；字典序最小需要最小堆，
时间会变为 O(E + V log V)。
- 先修关系是否可能重复？ 本题保证互不相同。如果不保证，可以保留重复边并同步累计入度，
或在建图时去重；不能只去重一侧，否则入度永远减不到零。
- 输入是否可能包含非法编号或自环？ 本题假设调用方已经校验。需要防御式 API 时，应先定义
报错还是返回空列表，避免把“输入无效”和“存在依赖环”混成同一种结果。
- 只需要一条顺序，还是全部合法顺序？ 一条顺序是线性图遍历；枚举全部顺序要在每一步尝试
所有零入度课程，最坏输出量接近阶乘级。
- 课程能否并行学习？ 基础题返回线性排列。若要最少学期数且每学期容量无限，应按队列层级
批量处理；如果课程有时长，则要在 DAG 上计算最长依赖路径。
- 规模能否放入内存？ 在
V <= 2000下邻接表足够直接。边无法全部放入内存时，需要外部存储
或分区处理，已经超出这道编码题的边界。
30 秒回答框架
“我会把每门课作为节点，把 [course, prerequisite] 建成 prerequisite -> course，并统计每门课的入度。先把所有零入度课程放进队列；每次取出一门课加入 结果，遍历它的后继并把入度减一，新变成零的课程再入队。队列里的课程恰好是当前所有先修要求都 已满足的未处理课程，所以按这个顺序选择始终安全。结束时如果结果长度等于课程数，就返回结果； 否则剩余节点包含环，返回空列表。邻接表方案的时间和额外空间都是 O(V + E)。”
分步骤深入解答
最直接的思路是反复扫描所有未选课程，找到先修课都已出现的课程。这种做法即使使用集合记录已 完成课程，每轮仍可能检查全部边；在长链输入中要做 V 轮，时间可能达到 O(VE)。瓶颈来自反复 重新计算同一依赖是否已经满足。
Kahn 算法把这项信息增量维护为入度。设 graph[u] 保存完成课程 u 后可能被释放的课程， indegree[v] 保存课程 v 尚未满足的直接先修课数。建图时遇到 [course, prerequisite]，把 course 加入 graph[prerequisite]，同时增加 indegree[course]。
算法维护两个不变量：
indegree[v]等于从尚未处理节点指向v的边数。- 队列包含且只包含所有尚未处理、剩余入度为零的课程。
初始统计显然满足第一个不变量，把全部零入度节点入队后也满足第二个。取出课程 u 时，它没有 来自未处理课程的先修约束，因此把它放进结果是安全的。删除 u 的影响等价于遍历 graph[u] 并减少每个后继的入度；某个后继第一次变成零时入队，两项不变量继续成立。
from collections import deque
def find_course_order(
num_courses: int,
prerequisites: list[list[int]],
) -> list[int]:
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prerequisite in prerequisites:
graph[prerequisite].append(course)
indegree[course] += 1
ready = deque(
course for course, degree in enumerate(indegree) if degree == 0
)
order: list[int] = []
while ready:
course = ready.popleft()
order.append(course)
for dependent in graph[course]:
indegree[dependent] -= 1
if indegree[dependent] == 0:
ready.append(dependent)
return order if len(order) == num_courses else []若所有课程都被取出，不变量保证每门课加入结果时其先修课都已经在前面，因此结果合法。若结果短于 V，剩余有限子图中每个节点的剩余入度都大于零。从任意节点不断沿一条入边向前追溯，有限节点 必然使某个节点重复出现，重复段构成有向环；所以不可能完成全部课程。这也说明长度检查同时完成了 环检测。
每个节点入队、出队至多一次，每条边在建图和释放后继时各处理一次，时间为 O(V + E)。 邻接表、入度数组、队列和结果合计占 O(V + E) 空间。这里使用 deque，因为从 Python 列表头部 pop(0) 会移动其余元素，可能把队列操作退化为线性时间。
对抗性验证应检查结果本身，而不只比较某个固定答案：结果必须包含恰好 V 个不重复编号，并且 每个 [course, prerequisite] 中 prerequisite 的位置都小于 course。测试集至少包括空输入、 单节点、全部独立、单条长链、菱形依赖、多个互不连通分量和有向环。菱形图尤其能防止把“任意合法 顺序”误写成“必须匹配一个固定数组”。
DFS 也能完成拓扑排序：用白、灰、黑三色标记，遇到指向灰色节点的边即发现环，节点退出递归时 加入结果，最后反转后序。它适合同时返回一条具体环路径，但 Python 中长链可能触发递归深度限制。 Kahn 算法直接暴露“当前可学课程集合”，更容易扩展到并行学期，因此是本题更直接的首选。若规模 很小且题目只问可行性，反复扫描的简单方案可以更短；面试中应明确它的最坏复杂度，而非把它包装成 线性算法。
高质量示范回答
“我先确认只需返回任意合法顺序，并假设课程编号和依赖边都有效且不重复。每个关系 [course, prerequisite] 表示一条从先修课指向课程的边。这样，课程的入度就是还有多少直接先修课 没有完成。
我会建立邻接表和入度数组，把所有入度为零的课程加入 deque。循环中从队首取一门课放入答案， 再遍历它的后继，把这些后继的入度减一；只有在入度刚变成零时才入队。关键不变量是：队列中恰好 是当前没有未完成先修要求的课程，所以每次选择都不会违反依赖。
循环结束后不能无条件返回。答案长度等于课程总数时，所有依赖都满足；长度不足时，剩余节点都还有 入边，在有限图中沿入边追溯一定会回到访问过的节点，因此存在环，我返回空列表。
邻接表让每个节点和每条边只被处理常数次，时间为 O(V + E)，空间也是 O(V + E)。我会用空图、 单节点、长链、菱形多解、断开的分量和二节点环测试。验证多解时，我会检查每条先修边的相对位置， 不会把结果限定成某一个固定排列。”
常见错误
- 把边建成
course -> prerequisite→ 输出可能把课程放在先修课之前 → **按“完成哪个节点会释放
哪些节点”建立 prerequisite -> course。**
- 只从课程 0 开始遍历 → 独立分量会被漏掉 → 初始化时扫描全部节点，把所有零入度节点入队。
- 队列为空就返回部分结果 → 有环输入被误报为成功 → **只有
len(order) == num_courses才返回
顺序。**
- 同一节点多次入队 → 结果出现重复课程 → 只在入度从 1 降到 0 的那一次入队。
- 用
list.pop(0)实现队列 → 长输入中反复移动元素 → 使用deque.popleft()。 - 拿输出和一个固定拓扑序比较 → 另一条合法顺序被判错 → 检查唯一性、长度和每条边的相对位置。
- 图去重但入度不去重，或反过来 → 重复边契约下计数不一致 → **要么完整保留重复边，要么建图时
对边统一去重。**
- 声称额外空间是
O(V)→ 邻接表还保存了全部边 → 按稀疏图实现报告O(V + E)。 - 用 DFS 却没有访问中状态 → 环上的节点会被重复递归或错误完成 → **至少使用三色状态区分正在
访问和已经完成。**
追问及应对
追问 1：如何返回字典序最小的合法顺序？
把普通队列替换成最小堆。每次从所有当前零入度课程中取编号最小者，就能通过贪心交换论证得到 字典序最小结果。边处理仍为 O(E)，节点入堆和出堆使时间变为 O(E + V log V)；如果只需任意 顺序，普通队列更简单且更快。
追问 2：如果每学期可以同时学习任意多门课程，最少需要几个学期？
按队列的当前长度分层处理：一层中的课程在这一学期同时完成，它们释放的零入度后继进入下一层。 每完成一层，学期数加一。这个结论依赖所有课程耗时相同且并发容量无限；若每学期最多选 k 门课， 简单分层不再保证全局最优。
追问 3：每门课程耗时不同，怎样得到最早毕业时间？
先取得拓扑序，再按该顺序做 DAG 动态规划。课程的最早开始时间是所有先修课最早完成时间的最大值， 加上自身耗时得到最早完成时间。答案是全部课程最早完成时间的最大值。不能直接用 Kahn 算法的层数， 因为一门耗时十周的课和一门耗时一周的课并不等价。
追问 4：如何返回导致失败的一条具体依赖环？
Kahn 算法能判断剩余子图有环，但不会直接保留环路径。可以在剩余节点上运行三色 DFS，并记录父节点； 遇到指向灰色节点的边时，沿父指针回溯即可构造一条环。若诊断信息是核心需求，也可以从一开始使用 带父指针的 DFS 拓扑排序。
追问 5：不断新增依赖边时，如何维护顺序？
低频更新时，加入新边后重新运行 O(V + E) 拓扑排序最可靠，也最容易验证。更新频繁且图很大时， 可以维护节点当前位置：若新边已符合当前顺序，无需调整；否则只在受影响区间内检查可达性并重排。 动态拓扑排序实现复杂，面试中应先用更新频率和图规模证明它值得引入。
追问 6：如何枚举所有合法学习顺序？
使用回溯：每一步枚举所有当前零入度节点，暂时选择一个、更新后继、递归，再恢复入度。它会避免输出 非法排列，但合法顺序数量本身可能接近 V!，所以时间至少与输出规模成正比。需要先确认上限很小， 并讨论是否只需计数、采样或前 k 个结果。