题目描述
思路解析
一句话答案：LeetCode 207 课程表本质是判断先修依赖图有没有环，标准解是 BFS 拓扑排序（Kahn 算法）：统计每门课的入度，入度为 0 的课先入队，出队修掉后把它指向的后继课入度减一，减到 0 就入队；最终修掉的课数等于总课数说明无环、能修完。时间与空间都是 O(V+E)。
课程表这道题真正在问什么
共 numCourses 门课，prerequisites 里每一对 [b, a] 表示修 b 之前必须先修 a，问能否把所有课修完。把每门课看作节点、每条先修关系看作从 a 指向 b 的有向边（先修指向后修），问题就翻译成：这张有向图能否排出一个不违反任何箭头的线性顺序。答案取决于一件事——图里有没有环：课程互相等待形成死锁，谁都修不了；无环则一定存在合法顺序。所以这题真正问的是「有向图判环」。
为什么想到拓扑排序和入度
顺着生活直觉走：制定学习计划时，第一批修的必然是「没有任何先修要求」的课。翻译到图上，就是入度为 0 的节点——入度指有几条边指向它，也就是它还剩几门先修没满足。
修完一门课，它对后继课的约束就解除了，相当于把它的出边全部擦掉，后继课的入度各减一；谁的入度减到 0，谁就获得了「可以修」的资格。反复执行「取一门入度 0 的课修掉、给后继减入度」，就是 Kahn 算法的 BFS 拓扑排序：用队列装着当前所有可修的课，出队一门、松动一批，直到队列耗尽。
队列维护的不变量与每步的正确性
整个过程保持一条不变量：队列里的课，先修要求全部已被修掉，随时可修。出队修掉它不会违反任何约束；给后继入度减一，则如实记录「又一门先修被满足」。每门课恰好在入度归零那一刻入队一次，每条边恰好在起点被修掉时处理一次，既不重复也不遗漏。
建图方向是最高频的错误：[b, a] 要建 a 指向 b 的边、给 b 的入度加一。方向一反，整个先修关系颠倒，拓扑序全错。记住口诀「先修指向后修」即可。
为什么用修课计数判环而不是看队列空
队列空只说明「没有课可修了」，不说明「课都修完了」。若图里有环，环上每门课都在等环上另一门课先修完，入度永远大于 0，一辈子进不了队——队列会提前耗尽，而这些课一门也没修掉。所以必须数一数总共出队了多少门课：计数等于 numCourses 才是真的全部修完（无环），小于则说明剩下的课困在环里，返回 false。
顺带一提，简单的 visited 标记判不出有向环，要么像这样用入度加计数，要么改用 DFS 三色标记法：搜索中遇到「正在访问中」的灰色节点，说明走回了当前路径，即有环。
复杂度怎么数，还有哪些变体
时间 O(V+E)：V 门课每门入队出队至多一次，E 条边在起点出队时各处理一次；空间 O(V+E)，花在邻接表、入度数组和队列上。
两个延伸：LeetCode 210 要求给出一个合法学习顺序，做法完全一样，把每次出队的课依次记进数组，最后长度够就返回它；另外若输入含重复的先修边，入度会被多算导致误判，健壮的做法是建图时先对边去重。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「入度为 0 入队 → 出队修掉 → 后继入度减一 → 减到 0 再入队」，下面每一步都在套它。
第 0 步 · 统计入度：先数入度：每个节点头顶标着「有几门课指向它」。入度 0 的课没有先修、可以立刻修——这里是 0 和 1。
入队 · 入度0 的课：把入度为 0 的 0、1 放进队列（标记为「待修」）。它们是整个学习计划的起点。
出队 · 修课 0：从队首取出课 0，把它修掉（高亮）。它入度为 0，先修都满足了，现在轮到它。
减后继入度 · 0→2/3：课 0 修完，记入学习顺序。它指向的后继课 2、3 入度各减一——2 减到 0 了！
新课入队 · 2：把刚减到 0 入度的 2 入队，等着被修。队列现在是 [1, 2]。
出队 · 修课 1：从队首取出课 1，把它修掉（高亮）。它入度为 0，先修都满足了，现在轮到它。
减后继入度 · 1→3/4：课 1 修完，记入学习顺序。它指向的后继课 3、4 入度各减一——3、4 减到 0 了！
新课入队 · 3,4：把刚减到 0 入度的 3、4 入队，等着被修。队列现在是 [2, 3, 4]。
出队 · 修课 2：从队首取出课 2，把它修掉（高亮）。它入度为 0，先修都满足了，现在轮到它。
减后继入度 · 2→5：课 2 修完，记入学习顺序。它指向的后继课 5 入度各减一。
队列状态：这一轮没有新的课入度减到 0，没有新课入队。队列现在是 [3, 4]，继续修下一门。
出队 · 修课 3：从队首取出课 3，把它修掉（高亮）。它入度为 0，先修都满足了，现在轮到它。
减后继入度 · 3→5：课 3 修完，记入学习顺序。它指向的后继课 5 入度各减一。
队列状态：这一轮没有新的课入度减到 0，没有新课入队。队列现在是 [4]，继续修下一门。
出队 · 修课 4：从队首取出课 4，把它修掉（高亮）。它入度为 0，先修都满足了，现在轮到它。
减后继入度 · 4→5：课 4 修完，记入学习顺序。它指向的后继课 5 入度各减一——5 减到 0 了！
新课入队 · 5：把刚减到 0 入度的 5 入队，等着被修。队列现在是 [5]。
出队 · 修课 5：从队首取出课 5，把它修掉（高亮）。它入度为 0，先修都满足了，现在轮到它。
减后继入度 · 5→—：课 5 修完，记入学习顺序。它指向的后继课 （无） 入度各减一。
队列状态：这一轮没有新的课入度减到 0，没有新课入队。队列现在是 [空]，继续修下一门。
完成 · 全部修完：队列空了，一共修掉 6 门课 = 总课数 6 → 无环，能全部修完！一条合法学习顺序是 0 → 1 → 2 → 3 → 4 → 5。
边界先想清：无依赖全 true；一旦有环（哪怕两门课互相先修）就 false；判定标准始终是「修掉数 == 总数」。
三个高频追问：输出具体顺序(LC210)、BFS vs DFS 判环、以及重复边的处理。
参考代码
from collections import dequedef canFinish(numCourses, prerequisites): g = [[] for _ in range(numCourses)] indeg = [0] * numCourses for b, a in prerequisites: # 修 b 前先修 a g[a].append(b); indeg[b] += 1 q = deque(i for i in range(numCourses) if indeg[i] == 0) seen = 0 while q: u = q.popleft(); seen += 1 # 修掉 u for v in g[u]: indeg[v] -= 1 # 后继入度减一 if indeg[v] == 0: q.append(v) return seen == numCourses # 修完=无环复杂度
- 时间：O(V + E)，每个点入队出队一次，每条边松弛一次
- 空间：O(V + E)，邻接表 O(V+E) + 入度数组与队列 O(V)
易错点
面试追问把动画讲成自己的话
追问要求输出一个合法的学习顺序（LC210）怎么办？
追问BFS 拓扑和 DFS 判环有什么区别？
追问如果有重复的先修边会出问题吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
课程表 II
LeetCode 210 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题