题目重点：Kahn 入度队列每次移除零入度节点，既能判断是否有环，也能构造一个合法拓扑顺序。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入边 (u,v) 表示 u 必须在 v 之前；允许多条相同边，并按每条边同步计算/减少入度。
- 有环返回 None，无环返回任意一个合法顺序；空图返回空列表。
- 若题目要求字典序最小合法顺序，要把队列改为最小堆。
解题路线
- 构建邻接表与入度数组，将所有入度 0 节点入队。
- 逐个取出节点加入输出，并对每条出边的目标入度减 1；降为 0 的节点入队。
- 若最后输出 n 个节点，所有前驱都先于后继；若少于 n 个，余图无零入度节点，有限有向图中必含环。
- 单纯 DFS 判环可回答是否可排，追问输出顺序时要在回溯后序反转；Kahn 直接产生顺序且易观察未处理节点。
手动走一遍
边 0→2、1→2、2→3，初始零入度为 0、1，可输出 [0,1,2,3] 或 [1,0,2,3]。若再加 3→1，则处理 0 后没有可继续的零入度点，返回 None。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Return one topological order; reject a directed graph containing a cycle."""
from collections import deque
def topological_order(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
if n < 0:
raise ValueError("negative vertex count")
graph = [[] for _ in range(n)]
indegree = [0] * n
for before, after in edges:
if not 0 <= before < n or not 0 <= after < n:
raise ValueError("vertex outside range")
graph[before].append(after)
indegree[after] += 1
ready = deque(v for v in range(n) if indegree[v] == 0)
result = []
while ready:
node = ready.popleft()
result.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
ready.append(neighbor)
return result if len(result) == n else None
复杂度
n 点 m 边：建图与遍历 O(n+m) 时间、O(n+m) 空间；若要求字典序最小而用堆，时间 O((n+m) log n)。
易错点与追问
容易失分的边界
- 只有判环布尔值，没有构造输出顺序以回答追问。
- 误把边方向 (u,v) 解为 v 在 u 前。
- 边重复时建图保留两条却入度只加一次，导致错误提前入队。
- 部分节点有环时返回局部顺序并称完整答案。
继续深挖
- 如何输出字典序最小的拓扑顺序？
- 如何返回环上的一条证据路径？
- 动态图不断新增依赖边时是否能增量维护顺序？
