题目描述
有些课要先修另一门才能上。给定先修关系，判断能否修完所有课。
课程 = 0,1,2,3
先修 = 学1先学0；学2先学1；学3先学1
输出 = true
思路解析
怎么存这张图？用邻接表：graph[b] 列出「学完 b 之后能解锁哪些课」。同时为每门课记一个入度。
入度 = 指向它的箭头数 = 还有几门前置课没学。入度 0 = 没有前置 = 现在能学。学完它，就把它指向的课入度各减 1。
建图 + 算入度：画出图、标好每个节点入度。只有课 0 入度为 0，先放进队列。
入度记录每门课「还有几门前置没学」：课0=0(无前置)，课1/2/3 各=1。只有入度为 0 的能马上学。
学 0：从队列取出 0 学完。它指向的课 1 入度 −1 变成 0——课 1 也能学了，入队。已学：0。
学 1：取出 1 学完。它指向的 2 和 3 入度都减到 0，双双入队。已学：0、1。
学 2、3：依次取出 2、3 学完，它们没有后续课。队列空了。
判断：4 门全部成功出队 → 没有环，能学完，返回 true。(若有环，环上的课入度永远减不到 0，会卡住)
凡是「有依赖顺序、判断能否排出顺序/有无环」，都是拓扑排序：课程表 II、任务调度都靠它。
参考代码（Python）
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 只多记一个出队顺序当答案。
Python
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）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。