题目描述
有些课要先修另一门才能上。给定先修关系，判断能否修完所有课。
思路解析
最朴素的做法：每轮扫一遍所有课，找还没学、且前置都学完的去学。可每轮都要把每门课的前置重新检查一次，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、任务调度都靠它。
参考代码（Python）
1indeg = [0]*n; graph = defaultdict(list)
2for a, b in prerequisites: # 学 a 前要先学 b
3 graph[b].append(a); indeg[a] += 1
4q = deque(i for i in range(n) if indeg[i]==0) # 入度0先入队
5cnt = 0
6while q:
7 cur = q.popleft(); cnt += 1
8 for nxt in graph[cur]:
9 indeg[nxt] -= 1 # 前置课少一门
10 if indeg[nxt] == 0: q.append(nxt)
11return cnt == n # 全部出队才无环复杂度分析
- 时间复杂度：O(V+E) —— 每个节点和边各处理一次
- 空间复杂度：O(V+E) —— 邻接表 + 入度 + 队列
套路模板
记住骨架：建图算入度、入度0入队、出队就给邻居减度、最后数 cnt==n 判环。课程表 II 只多记一个出队顺序当答案。
1# 「有依赖顺序，判能否排序 / 有无环」都套
2indeg = [0]*n; g = defaultdict(list)
3for u, v in 依赖: g[u].append(v); indeg[v] += 1 # u→v
4q = deque(i for i in range(n) if indeg[i]==0)
5cnt = 0
6while q:
7 x = q.popleft(); cnt += 1
8 for y in g[x]:
9 indeg[y] -= 1
10 if indeg[y]==0: q.append(y)
11return cnt == n # 全出队才无环易错点
- 错误写法：建图方向搞反 → 正确写法：[a,b] 表示先学 b → 边 b→a（方向反了入度全错）
- 错误写法：只判断队列空就返回 true → 正确写法：要数出队个数 cnt == n（有环时环上节点出不了队，cnt < n）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。