题目重点：Kahn给出顺序，失败后用显式DFS栈提取闭环，避免把所有残留节点误当环。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练边采用(before,after)，课程编号0..n-1；LeetCode常见(course,prerequisite)须先反向。
- 返回一个闭环即可，不枚举所有环或保证最短；重边按重复依赖一致处理。
解题路线
- 建立before到after邻接和入度，0入度课程入队，处理课程后减少后继入度。全部n个出队则顺序满足每条依赖。
- 若处理不足n，残留包含有向环；残留还可能包含环下游的无环节点，例如0↔1→2，不能把所有残留节点都称为环。
- 用白/灰/黑标记DFS。灰节点位于当前path，边指向灰节点时截取path从该节点开始的后缀并再追加起点，给出真实闭环；指向黑节点不是回边证据。
- 代码用显式迭代器栈，避免长课程链超过递归深度。灰节点的位置表在退出时删除，与path保持一致；多连通分量逐一启动。
- Kahn正确性来自每次仅输出所有前驱已处理的节点；DAG必有0入度点。反之剩余有限图每点有残留前驱，沿前驱追踪必重复，证明存在环。
手动走一遍
训练依赖0→1、1→0、1→2，返回闭环[0,1,0]，2虽处理不了但不在环上；空图返回空顺序且无环。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def course_order_or_cycle(n, prerequisites):
"""Each edge is (before, after); return (order, None) or (None, closed cycle)."""
if n < 0:
raise ValueError("negative course count")
graph=[[] for _ in range(n)]
degree=[0]*n
for before,after in prerequisites:
if not (0 <= before < n and 0 <= after < n):
raise ValueError("invalid course")
graph[before].append(after)
degree[after]+=1
ready=deque(i for i in range(n) if degree[i]==0)
order=[]
while ready:
at=ready.popleft()
order.append(at)
for nxt in graph[at]:
degree[nxt]-=1
if degree[nxt]==0: ready.append(nxt)
if len(order)==n:
return order,None
color=[0]*n
for root in range(n):
if color[root]: continue
path=[root]
position={root:0}
color[root]=1
stack=[(root,iter(graph[root]))]
while stack:
at,neighbors=stack[-1]
nxt=next(neighbors,None)
if nxt is None:
stack.pop()
path.pop()
position.pop(at)
color[at]=2
elif color[nxt]==0:
color[nxt]=1
position[nxt]=len(path)
path.append(nxt)
stack.append((nxt,iter(graph[nxt])))
elif color[nxt]==1:
return None,path[position[nxt]:]+[nxt]
raise AssertionError("cycle must exist")
复杂度
O(n+e)时间与空间；返回所有环可能指数级，不属于本合同。
易错点与追问
容易失分的边界
- 边方向反了。
- 把Kahn残留全体当一个环。
- 灰黑标记混用。
继续深挖
- 需要字典序最小修课顺序？
- 打印所有属于任意环的课程怎样用SCC？
- 在线新增依赖如何检测？
