题目重点：用Kahn拓扑排序判断前置课程是否可完成，纠正图遍历复杂度和边方向。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练课程0..n−1，pair(course,prerequisite)表示先修→课程；重复pair只一条依赖，自环不可完成。返回一个order或None，n0返回[]。
- 无特定变体约束时按明确训练合同实现，BFS与DFS都合法；不声称DFS在所有输入上空间必更省。
解题路线
- 构adj[prerequisite]→course，indegree[course]加1。所有入度0课程共同入queue，每出队一个就删除其对后继的依赖。
- 后继入度到0才入队，保证全部前置已在结果。最终处理n个则成功；有剩余表示某环阻止消除，不是简单“还有没访问节点”。
- 为何剩余必有环？有限残余图若每节点入度>0，沿前置不断走必重复节点；无环图总有入度0起点。循环消除不会把环节点错误当完成。
- 边去重前不能重复增入度后却用set邻接只减一次，否则无环图会残余假环。ID与边方向先复述，小例子比复杂代码更能暴露写反。
手动走一遍
n3，(1,0),(2,1)可order[0,1,2]；再加(0,2)成环返回None。两次同(1,0)仍一条前置，孤立课也必须出现在order。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def course_order(n,prerequisites):
"""Pair (course,prerequisite); duplicate edges dedup; cycle->None."""
if n<0:raise ValueError('nonnegative course count')
adjacent=[set() for _ in range(n)];indegree=[0]*n
for course,prerequisite in prerequisites:
if not 0<=course<n or not 0<=prerequisite<n:raise ValueError('course id')
if course not in adjacent[prerequisite]:
adjacent[prerequisite].add(course);indegree[course]+=1
queue=deque(i for i,d in enumerate(indegree) if d==0);order=[]
while queue:
prerequisite=queue.popleft();order.append(prerequisite)
for course in adjacent[prerequisite]:
indegree[course]-=1
if indegree[course]==0:queue.append(course)
return order if len(order)==n else None
复杂度
O(V+E)时间、O(V+E)邻接/入度/queue，E按不同依赖边计。BFS不是O(VE)；DFS递归栈最坏O(V)，BFS队列最坏O(V)，优劣依形状和运行时。
易错点与追问
容易失分的边界
- pair方向写反会给逆序。
- 重复edge的indegree与邻接存储不同步。
继续深挖
- 要求字典序最小order时，用最小heap选择可用课程增加logV成本。
- 要返回具体环，Kahn残余只能定位范围，需DFS颜色/父指针重构。
