拓扑排序：用一套模板秒杀leetcode「课程表」系列三连题

LeetCode 207. 课程表 × 210. 课程表 II × 1462. 课程表 IV（三题均为中等）｜ DFS 三色标记 + Kahn 双解法

关键词：拓扑排序 · DFS 三色标记 · Kahn · 位集 · LeetCode

写在前面：你在排课，系统在防死锁

假设你要给自己排一学期的课：

• 想学「机器学习」，得先学「线性代数」；
• 想学「线性代数」，得先学「微积分」；
• 想学「微积分」，得先学「线性代数」……？

最后这条显然不合理：没有一门课能先开始，因为你永远等不到它的前置课。这就是依赖关系里的「死锁」，计算机里叫环。

LeetCode 的 207、210、1462，问的都是这件事的变体：

好消息是：这三题共用一套模板。210 只是 207 的判环逻辑上多收集一行顺序；1462 只是把"判环"换成"算可达"。本文给出两套模板：DFS 三色标记和Kahn 入度 BFS，你会一次会三题 × 两种思路。

一、统一模板

1.1 核心概念：先修、入度、拓扑序

先修关系[a, b]表示：要学 a，必须先学 b（a 依赖 b）。

这里最关键的一个词是入度：

indeg[a]= a 还欠几门先修课。

用排课的话说：

• indeg[a] = 0：先修全齐，现在就能上；
• indeg[a] = 3：还欠 3 门，先修完再来；
• 环：谁都不为 0，永远没人能上。

把每门课按"欠债还清"的顺序排出来，就是拓扑序。注意：拓扑序不唯一——[0,1,2,3]和[0,2,1,3]都是对的，题目只要求任意一种。

1.2 统一建图：整套模板唯一的基建

三题、两种方法，建图只有一行差别都没有（1462 的方向小坑见 6.1），约定如下：

graph=defaultdict(list)indeg=[0]*numCoursesfora,binprerequisites:graph[b].append(a)# b 修完 → 解锁 a（边 b → a）indeg[a]+=1# a 的入度 = a 还欠几门先修

注意方向：先修 → 后修，即graph[b].append(a)（207/210 的元组里 a 是后修、b 是先修）。

⚠️ 这是全篇第一个坑：方向写反成graph[a].append(b)，207 判环碰巧没事，但 210 的输出顺序会整个颠倒。

1.3 判环的两种判据

同一张图，两套方法各用各的判环方式：

机制细节分别在第二、三章讲透，先记住结论即可。

1.4 三题 × 模板对应关系表

记住这张表的演进方向：判环 → 判环 + 收集 → 判环换可达。后面四五六节就是按这个顺序逐个实战。

二、方法一：DFS 三色标记

2.1 为什么是"三"色？两种颜色不够吗

先回答一个直觉问题：判环用"访问过 / 没访问过"两个标记不就够了吗？

不够。因为 DFS 递归展开时，一个节点其实有三种状态，少一种就漏判环：

为什么两种颜色不够？假如只有"访问过/没访问过"，当邻居 B 再次撞上 A 时，你分不清两种完全相反的情况：

• A 是"正在栈上的祖先" → 你从 A 出发绕回了 A →环；
• A 是"早已安全的过去式" → 撞上它只是剪枝机会 →没事。

举个最小例子：numCourses = 2，先修[[1,0],[0,1]]——1 依赖 0，0 又依赖 1，标准环。DFS 从 0 出发：0 → 1 → 0。如果只有"访问过"一个标记：第二次撞到 0 时，0 已经标记过，你会想"访问过了，跳过"，然后愉快地返回 True——环就被你放跑了。而三色版会先问："0 是灰吗？是！你还在栈上 → 环！"当场return False。

所以三色的分工是：灰 = 专门抓环，黑 = 专门剪枝，白是起点。三种状态缺一不可。

2.2 三色的两条铁律

color[u]=1# 进栈：染灰（0 → 1）...color[u]=2# 出栈：染黑（1 → 2，永久，永不回退）

两个细节记牢：

• 灰不用擦除：出栈时直接"升级"成黑。对比双集合版（path进栈add、出栈remove），少一个 remove，天然没有"漏删 path 误判环"的烦恼；
• 灰必须先于黑判断：color[u] == 1要写在color[u] == 2前面。写反的话，环上的节点会被当成"黑"直接返回 True，环就漏判了。

什么时候用三色、什么时候用 Kahn？决策方法统一放在第七章。

三、方法二：Kahn 入度 BFS

如果说 DFS 是"从深处找环"，那 Kahn 就是模拟真实的排课流程：

1. 找出所有入度 = 0的课（先修全齐），进队；
2. 上一门课 u，所有依赖 u 的课 v 的入度减一（帮别人还债）；
3. v 入度变成 0 → 解锁，进队；
4. 直到队空。

为什么"全上完"就必然无环？因为环里的课互相欠着：A 欠 B、B 欠 A，两个入度永远 ≥ 1，永远进不了队。所以：

能全部排完 ⇔ 没有环。

还有一个隐藏结论：每门课入度只减不增，只会进队一次。所以done == numCourses（或len(order) == numCourses）就能判断"是否排完"——不重不漏。

四、实战 207：课程表（判环）

4.1 题目大意

给定numCourses门课和先修关系prerequisites，判断能否学完所有课（有没有环）。

最小示例：

numCourses = 2, prerequisites = [[1,0]] → True （0 先修，1 依赖 0，能学完） numCourses = 2, prerequisites = [[1,0],[0,1]] → False （互为先修，死锁）

4.2 DFS 三色版

fromcollectionsimportdefaultdictclassSolution:defcanFinish(self,numCourses:int,prerequisites:list[list[int]])->bool:defdfs(u):ifcolor[u]==1:# 灰：递归栈上的祖先 → 环returnFalseifcolor[u]==2:# 黑：已确认安全 → 剪枝returnTruecolor[u]=1# 0 白 → 1 灰（进栈）forvingraph[u]:ifnotdfs(v):returnFalsecolor[u]=2# 1 灰 → 2 黑（出栈，永久安全）returnTruegraph=defaultdict(list)fora,binprerequisites:graph[b].append(a)color=[0]*numCourses# 0 白 / 1 灰 / 2 黑returnall(dfs(u)foruinrange(numCourses))

复杂度：时间O(V + E)，空间O(V + E)。

4.3 Kahn 版

fromcollectionsimportdefaultdictclassSolution:defcanFinish(self,numCourses:int,prerequisites:list[list[int]])->bool:graph=defaultdict(list)indeg=[0]*numCoursesfora,binprerequisites:graph[b].append(a)indeg[a]+=1queue=[iforiinrange(numCourses)ifindeg[i]==0]done=0whilequeue:new_queue=[]foruinqueue:done+=1# 每上一门课 +1forvingraph[u]:indeg[v]-=1ifindeg[v]==0:new_queue.append(v)# 先修全齐 → 解锁queue=new_queuereturndone==numCourses# 全上完 = 无环

复杂度：时间O(V + E)，空间O(V + E)。

4.4 本节注意点

• 边界自动处理：numCourses = 1或空prerequisites时，all(dfs(...))和done == n都会直接返回 True，不用特判；
• 方向别存反：207 判环不挑方向，写反碰巧没事——但这是给 210 埋雷（顺序会颠倒）。所以从第一题起就按graph[b].append(a)（先修 → 后修）写。

五、实战 210：课程表 II（判环 + 收集）

5.1 题目大意

和 207 同样的图，但要求输出任意一个合法的上课顺序；如果有环，返回空数组[]。

最小示例：

numCourses = 2, prerequisites = [[1,0]] → [0,1] （先上 0，再上 1） numCourses = 2, prerequisites = [[1,0],[0,1]] → [] （有环）

5.2 相对 207 的改动：每个版本只多两行

5.3 DFS 三色版

fromcollectionsimportdefaultdictclassSolution:deffindOrder(self,numCourses:int,prerequisites:list[list[int]])->list[int]:defdfs(u):ifcolor[u]==1:returnFalseifcolor[u]==2:returnTruecolor[u]=1forvingraph[u]:ifnotdfs(v):returnFalsecolor[u]=2order.append(u)# ① 后序收集returnTruegraph=defaultdict(list)fora,binprerequisites:graph[b].append(a)color=[0]*numCourses order=[]foruinrange(numCourses):ifnotdfs(u):return[]# 有环returnorder[::-1]# ② 后序是反拓扑序，必须反转

复杂度：时间O(V + E)，空间O(V + E)。

5.4 Kahn 版

Kahn 升级到 210 比 DFS 还省事，出队时收集即可，顺序天然正确、不用反转：

fromcollectionsimportdefaultdictclassSolution:deffindOrder(self,numCourses:int,prerequisites:list[list[int]])->list[int]:graph=defaultdict(list)indeg=[0]*numCoursesfora,binprerequisites:graph[b].append(a)indeg[a]+=1queue=[iforiinrange(numCourses)ifindeg[i]==0]order=[]whilequeue:new_queue=[]foruinqueue:order.append(u)# ① 210 只多这一行forvingraph[u]:indeg[v]-=1ifindeg[v]==0:new_queue.append(v)queue=new_queuereturnorderiflen(order)==numCourseselse[]# ② 排完才返回

复杂度：时间O(V + E)，空间O(V + E)。

5.5 为什么非要[::-1]？

因为我们把图存成b → a（先修 → 后修），而后序收集是"先递归完后继、再收集自己"——得到的 order 天然是后继在前、先修在后（比如[1, 0]）。反转一下就对了。

这一行就是 210 唯一的坑：忘了反转，[[1,0]]会输出[1,0]，顺序整个颠倒。Kahn 版没有这个问题。

六、实战 1462：课程表 IV（判环 → 算可达）

6.1 题目大意

给定queries[j] = [uj, vj]，回答uj 是不是 vj 的（直接或间接）先修课。先修图保证没有环，numCourses ≤ 100，queries ≤ 10⁴。

把"先修"翻译成图论语言，就是：从 uj 出发，沿着"先修 → 后修"的边能不能走到 vj——即有向可达（传递闭包）。

模板改动只有一处：判环整段退场，换成算可达——给每个节点维护一个reach集合，记下"我有哪些（直接/间接）先修"，查询时直接查集合。

⚠️方向小坑：1462 的元组顺序和 207 正好相反——[ai, bi]里ai 是先修、bi 是后修（207 的[a, b]里 a 是后修）。建图前先分清"谁是谁的先修"，方向错了答案全反。

最小示例：

numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]] queries = [[1,0],[1,2]] → [true, true] （1 → 2 → 0，所以 1 是 0 和 2 的先修）

6.2 对照组：朴素版（每个查询单独 DFS）

先看最直白的思路——每个查询从 u 出发 DFS 一次，能走到 v 就是 True：

fromcollectionsimportdefaultdictclassSolution:defcheckIfPrerequisite(self,numCourses:int,prerequisites:list[list[int]],queries:list[list[int]])->list[bool]:graph=defaultdict(list)fora,binprerequisites:graph[a].append(b)# 先修 → 后修（正向边）ans=[]foru,vinqueries:seen={u}stack=[u]found=Falsewhilestackandnotfound:x=stack.pop()foryingraph[x]:ify==v:found=Truebreakifynotinseen:seen.add(y)stack.append(y)ans.append(found)returnans

复杂度：时间O(Q × (V + E))，空间O(V + E)。代入最坏数据：10⁴ × (100 + 4950) ≈ 5 × 10⁷——能过，但每次都重跑，纯属浪费。

6.3 模板升级：三色 DFS + 位集

三色模板原样保留，只是"黑"的含义从"确认安全"升级成"先修集已算完"——这不就是现成的记忆化剪枝吗：

fromcollectionsimportdefaultdictclassSolution:defcheckIfPrerequisite(self,numCourses:int,prerequisites:list[list[int]],queries:list[list[int]])->list[bool]:defdfs(u):ifcolor[u]==1:# 灰：题目保证无环，此分支永不触发（保留模板完整）returnreach[u]ifcolor[u]==2:# 黑：先修集已算完 → 剪枝returnreach[u]color[u]=1# 白 → 灰forpingraph[u]:# graph[u] = u 的直接先修列表reach[u]|=dfs(p)|(1<<p)# 先修 p 和 p 的先修，都是 u 的先修color[u]=2# 灰 → 黑returnreach[u]graph=defaultdict(list)fora,binprerequisites:graph[b].append(a)# b 是后修：先修列表里放 a（和模板同一行建图）color=[0]*numCourses# 0 白 / 1 灰 / 2 黑reach=[0]*numCourses# reach[v] 二进制第 u 位 = u 是 v 的先修foruinrange(numCourses):dfs(u)return[bool((reach[v]>>u)&1)foru,vinqueries]

复杂度：时间O(V + E)+ 每查询O(1)，空间O(V + E)。

6.4 Kahn 版：拓扑序 + 位集传播

Kahn 的骨架一个字不改，只是把"判环"改成沿拓扑序传播先修集合。妙处在于：出队 u 时，所有先修都比 u 先出队，所以reach[u]已经是最终结果：

fromcollectionsimportdefaultdictclassSolution:defcheckIfPrerequisite(self,numCourses:int,prerequisites:list[list[int]],queries:list[list[int]])->list[bool]:graph=defaultdict(list)indeg=[0]*numCoursesfora,binprerequisites:graph[a].append(b)# 1462：a 先修 → b 后修（正向边，拓扑排序用）indeg[b]+=1queue=[iforiinrange(numCourses)ifindeg[i]==0]reach=[0]*numCourseswhilequeue:new_queue=[]foruinqueue:forvingraph[u]:reach[v]|=reach[u]|(1<<u)# u 和 u 的全部先修，都成了 v 的先修indeg[v]-=1ifindeg[v]==0:new_queue.append(v)queue=new_queuereturn[bool((reach[v]>>u)&1)foru,vinqueries]

复杂度：时间O(V + E)+ 每查询O(1)，空间O(V + E)。

6.5 位集为什么这么香

numCourses ≤ 100，1 << u一个位一门课，Python 大整数天然就是位集，零额外成本。

本节注意点：

• 判环逻辑可省：题目保证无环，“撞灰 = 环”"排不完 = 环"都不会触发；但三色版的灰判断建议保留——它和模板同构，万一题目条件变化也不会栈溢出；
• 方向别弄混：DFS 版存"先修列表"（graph[b].append(a)），Kahn 版存"正向边"（graph[a].append(b)），两个版本用途不同，各写各的（原因见 6.4 注释）。

七、方法对比：怎么选

什么时候用三色，什么时候用 Kahn？

优先选三色 DFS的三种场景：

1. 题目不止问"能不能排"，还问"谁安全 / 环在哪"——比如姊妹题 802. 找到最终安全状态，"黑 = 安全"直接就是答案，DFS 染完色结果就出来了，Kahn 还得绕；
2. 需要 DFS 后序 / 深度这类信息——后序天然是"子孙在前、自己靠后"，配合反转就是拓扑序，一鱼两吃；
3. 你想复用同一套模板刷其他图论题——"判环 + 染色 + 后序"是图论三件套，DFS 一次全带走。

优先选Kahn的场景：

1. 只想要拓扑序，别的信息一概不要——出队即收、顺序天然正确，不用反转；
2. 数据量很大、课程链很长——DFS 递归可能栈溢出，Kahn 无递归，天然安全；
3. 起手想好讲——"模拟排课还债"比"三色状态机"更接近生活直觉。

建议：默认起手 Kahn（好讲、无栈溢出），但一定要把三色版也练熟——遇到染色类变体题，它就是你的杀手锏。

八、总结：三题一张表，三个直觉一句话

8.1 三题总对比表

8.2 把这张图刻进脑子里

先修关系 [a, b]（a 依赖 b） │ graph[b].append(a) ← 唯一的建图 indeg[a] += 1 │ ┌─────────────┴─────────────┐ ▼ ▼ DFS 三色标记 Kahn 入度 0 白 → 1 灰 → 2 黑 只上入度0 撞灰 = 环 排不完 = 环 染黑 = 安全剪枝 / 已算完 │ │ └────────┬──────────────────┘ ▼ 207：判环 → True / False 210：判环 + 收集 → order / []（Kahn 直接收，DFS 记得 [::-1]） 1462：判环换成算可达 → 位集布尔数组（黑 = 已算完，拓扑序传播）