题目描述
思路解析动画文字版
最朴素的做法：每轮扫一遍所有课，找还没学、且前置都学完的去学。可每轮都要把每门课的前置重新检查一次，n 门课最坏扫 n 轮——大量重复。
转折：与其每轮重数，不如给每门课维护一个入度（指向它的箭头数 = 还有几门前置没学）。学完一门课，只把它直接解锁的课入度各减 1；谁减到 0，就立刻能学、入队。这样每条边只用一次，不再重复扫。
建图 + 算入度：邻接表 graph[0]=[2]、graph[1]=[2]、graph[2]=[3]，并数出入度：课 0、1 没前置（0），课 2 等两门（2），课 3 等一门（1）。
入度 0 先入队：把所有入度为 0 的课入队：0 和 1 都没前置，先放进队列，作为「现在就能学」的起点。
出队 0 · 学它：取出 0 学完，已学 cnt=1。接下来看它解锁了哪些课（graph[0]=[2]）。
0→2 减入度（负例：没到 0，不入队）：沿边 0→2，把课 2 入度 −1：2 还没到 0（还差课 1）——所以课 2 暂不入队。这一步很关键：减入度 ≠ 立即入队，只有归零才入队。
出队 1 · 学它：再取出 1 学完，cnt=2。它也解锁课 2（graph[1]=[2]）。
1→2 减入度（这次归 0 → 入队）：沿边 1→2，课 2 入度 1→0：两门前置都学完了！课 2 现在入队。对比上一步——同样是减入度，这次归零所以入队。
出队 2 → 3 入度归 0：取出 2 学完，cnt=3。沿 2→3，课 3 入度 1→0，入队。
出队 3 · 全部学完：取出 3，cnt=4 = 课程总数 n。4 门全部成功出队 → 没有环，返回 true。若图里有环，环上的课入度永远减不到 0、进不了队，最终 cnt < n，就返回 false。
凡是「有依赖顺序、判断能否排出顺序/有无环」，都是拓扑排序：课程表 II、任务调度都靠它。
迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
边界三连：边界三连：极端输入先过一遍。
几个高频追问，记住答法。
参考代码
class Solution: def canFinish(self, numCourses, prerequisites): graph = [[] for _ in range(numCourses)] indeg = [0] * numCourses for a, b in prerequisites: graph[b].append(a) indeg[a] += 1 q = [i for i in range(numCourses) if indeg[i] == 0] head = 0 seen = 0 while head < len(q): cur = q[head] head += 1 seen += 1 for nxt in graph[cur]: indeg[nxt] -= 1 if indeg[nxt] == 0: q.append(nxt) return seen == numCourses复杂度
- 时间复杂度：O(V+E)，每个节点和边各处理一次
- 空间复杂度：O(V+E)，邻接表 + 入度 + 队列
可套用的代码模板
记住骨架：建图算入度、入度0入队、出队就给邻居减度、最后数 cnt==n 判环。课程表 II 只多记一个出队顺序当答案。
# 「有依赖顺序，判能否排序 / 有无环」都套indeg = [0]*n; g = defaultdict(list)for u, v in 依赖: g[u].append(v); indeg[v] += 1 # u→vq = deque(i for i in range(n) if indeg[i]==0)cnt = 0while q: x = q.popleft(); cnt += 1 for y in g[x]: indeg[y] -= 1 if indeg[y]==0: q.append(y)return cnt == n # 全出队才无环易错点
面试追问把动画讲成自己的话
追问拓扑排序的两种实现？
追问怎么判断有环？
追问复杂度？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
课程表 II
LeetCode 210 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题