课程表 II
Course Schedule II
本机进度仅保存在当前浏览器
题目描述
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给定课程总量和先修关系 prerequisites，返回你为了学完所有课程所安排的学习顺序（可能有多个正确答案，返回任意一种）；不可能完成则返回空数组。
示例：numCourses = 4，prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]，输出 [0, 1, 2, 3]（或 [0, 2, 1, 3]）。
解题思路
- 在第 207 题 Kahn 算法的基础上，把"出队顺序"记录下来就是拓扑序。
- 每次从队列取出的节点，其全部先修节点都已输出，因此追加到结果末尾总是合法的。
- 结果长度不足 numCourses 说明存在环，按题意返回空数组。
参考实现
查看参考实现Python · 建议先自行作答
from collections import deque
def findOrder(numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
indeg = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indeg[a] += 1
queue = deque(i for i in range(numCourses) if indeg[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []