课程表
Course Schedule
本机进度仅保存在当前浏览器
题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。有些课程有先修课程要求，用 prerequisites[i] = [a, b] 表示想学课程 a 必须先完成课程 b。判断是否可能完成所有课程的学习。
示例：numCourses = 2，prerequisites = [[1, 0]]，输出 true；prerequisites = [[1, 0], [0, 1]]，输出 false（互相依赖成环）。
解题思路
- 建模为有向图：b -> a 表示先修边；"能修完所有课"等价于图中无环。
- Kahn 算法（BFS 拓扑排序）：统计各点入度，入度为 0 的节点入队，出队时把它指向的节点入度减一，减到 0 再入队。
- 最终出队节点数等于总节点数则无环；有环时环内节点入度永远无法降到 0，会被剩余下来。
参考实现
查看参考实现Python · 建议先自行作答
from collections import deque
def canFinish(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)
taken = 0
while queue:
node = queue.popleft()
taken += 1
for nxt in graph[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
queue.append(nxt)
return taken == numCourses