尧图网页设计 
LeetCode 207. 课程表 × 210. 课程表 II × 1462. 课程表 IV三题均为中等 DFS 三色标记 Kahn 双解法关键词拓扑排序 · DFS 三色标记 · Kahn · 位集 · LeetCode写在前面你在排课系统在防死锁假设你要给自己排一学期的课想学「机器学习」得先学「线性代数」想学「线性代数」得先学「微积分」想学「微积分」得先学「线性代数」……最后这条显然不合理没有一门课能先开始因为你永远等不到它的前置课。这就是依赖关系里的「死锁」计算机里叫环。LeetCode 的 207、210、1462问的都是这件事的变体题号难度问法本质207. 课程表中等能不能学完有没有环210. 课程表 II中等按什么顺序学输出拓扑序1462. 课程表 IV中等u 是不是 v 的先修有向可达传递闭包好消息是这三题共用一套模板。210 只是 207 的判环逻辑上多收集一行顺序1462 只是把判环换成算可达。本文给出两套模板DFS 三色标记和Kahn 入度 BFS你会一次会三题 × 两种思路。一、统一模板1.1 核心概念先修、入度、拓扑序先修关系[a, b]表示要学 a必须先学 ba 依赖 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约定如下graphdefaultdict(list)indeg[0]*numCoursesfora,binprerequisites:graph[b].append(a)# b 修完 → 解锁 a边 b → aindeg[a]1# a 的入度 a 还欠几门先修注意方向先修 → 后修即graph[b].append(a)207/210 的元组里 a 是后修、b 是先修。⚠️ 这是全篇第一个坑方向写反成graph[a].append(b)207 判环碰巧没事但 210 的输出顺序会整个颠倒。1.3 判环的两种判据同一张图两套方法各用各的判环方式方法判环依据一句话DFS 三色标记撞到灰 环递归栈上的祖先 灰绕回自己就是环Kahn 入度 BFS排不完 环环里的课互相欠债永远进不了队机制细节分别在第二、三章讲透先记住结论即可。1.4 三题 × 模板对应关系表题目难度问法模板用法DFS 三色版Kahn 版207中等能不能学完原样判环撞灰 环 → True/False排不完 环 →done n210中等按什么顺序学判环 收集染黑时order.append[::-1]出队即收 len n1462中等u 是 v 的先修判环 → 算可达位集黑 已算完向上合并拓扑序传播位集记住这张表的演进方向判环 → 判环 收集 → 判环换可达。后面四五六节就是按这个顺序逐个实战。二、方法一DFS 三色标记2.1 为什么是三色两种颜色不够吗先回答一个直觉问题判环用访问过 / 没访问过两个标记不就够了吗不够。因为 DFS 递归展开时一个节点其实有三种状态少一种就漏判环状态代码含义白0还没访问过灰1正在递归栈上当前探索路径上的祖先黑2已探索完确认安全为什么两种颜色不够假如只有访问过/没访问过当邻居 B 再次撞上 A 时你分不清两种完全相反的情况A 是正在栈上的祖先 → 你从 A 出发绕回了 A →环A 是早已安全的过去式 → 撞上它只是剪枝机会 →没事。举个最小例子numCourses 2先修[[1,0],[0,1]]——1 依赖 00 又依赖 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 就是模拟真实的排课流程找出所有入度 0的课先修全齐进队上一门课 u所有依赖 u 的课 v 的入度减一帮别人还债v 入度变成 0 → 解锁进队直到队空。为什么全上完就必然无环因为环里的课互相欠着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 黑出栈永久安全returnTruegraphdefaultdict(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:graphdefaultdict(list)indeg[0]*numCoursesfora,binprerequisites:graph[b].append(a)indeg[a]1queue[iforiinrange(numCourses)ifindeg[i]0]done0whilequeue:new_queue[]foruinqueue:done1# 每上一门课 1forvingraph[u]:indeg[v]-1ifindeg[v]0:new_queue.append(v)# 先修全齐 → 解锁queuenew_queuereturndonenumCourses# 全上完 无环复杂度时间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 的改动每个版本只多两行版本改①改②DFS 三色染黑时order.append(u)后序收集有环return []最后return order[::-1]Kahn出队时order.append(u)return order if len(order) numCourses else []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)# ① 后序收集returnTruegraphdefaultdict(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]:graphdefaultdict(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)queuenew_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 ≤ 100queries ≤ 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 就是 TruefromcollectionsimportdefaultdictclassSolution:defcheckIfPrerequisite(self,numCourses:int,prerequisites:list[list[int]],queries:list[list[int]])-list[bool]:graphdefaultdict(list)fora,binprerequisites:graph[a].append(b)# 先修 → 后修正向边ans[]foru,vinqueries:seen{u}stack[u]foundFalsewhilestackandnotfound:xstack.pop()foryingraph[x]:ifyv:foundTruebreakifynotinseen: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)|(1p)# 先修 p 和 p 的先修都是 u 的先修color[u]2# 灰 → 黑returnreach[u]graphdefaultdict(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]:graphdefaultdict(list)indeg[0]*numCoursesfora,binprerequisites:graph[a].append(b)# 1462a 先修 → b 后修正向边拓扑排序用indeg[b]1queue[iforiinrange(numCourses)ifindeg[i]0]reach[0]*numCourseswhilequeue:new_queue[]foruinqueue:forvingraph[u]:reach[v]|reach[u]|(1u)# u 和 u 的全部先修都成了 v 的先修indeg[v]-1ifindeg[v]0:new_queue.append(v)queuenew_queuereturn[bool((reach[v]u)1)foru,vinqueries]复杂度时间O(V E) 每查询O(1)空间O(V E)。6.5 位集为什么这么香朴素版逐查询 DFS模板版位集预处理无O(V E) 一遍搞定单个查询O(V E) 重跑一次O(1)一个移位 一个与运算Q 10⁴ 总开销≈ 5 × 10⁷≈ 5 × 10³ 10⁴numCourses ≤ 1001 u一个位一门课Python 大整数天然就是位集零额外成本。本节注意点判环逻辑可省题目保证无环“撞灰 环”排不完 环都不会触发但三色版的灰判断建议保留——它和模板同构万一题目条件变化也不会栈溢出方向别弄混DFS 版存先修列表graph[b].append(a)Kahn 版存正向边graph[a].append(b)两个版本用途不同各写各的原因见 6.4 注释。七、方法对比怎么选DFS 三色标记Kahn入度 BFS核心染灰染黑抓环模拟排课还债判环依据撞到灰 环排不完 环210 收集后序 [::-1]出队即收递归深度可能栈溢出课程链很长时无递归天然安全可读性稍绕要理解三色直观生活类比通用性好判环、染色、后序802 同源中只能剥洋葱信息量少什么时候用三色什么时候用 Kahn优先选三色 DFS的三种场景题目不止问能不能排还问谁安全 / 环在哪——比如姊妹题 802. 找到最终安全状态黑 安全直接就是答案DFS 染完色结果就出来了Kahn 还得绕需要 DFS 后序 / 深度这类信息——后序天然是子孙在前、自己靠后配合反转就是拓扑序一鱼两吃你想复用同一套模板刷其他图论题——判环 染色 后序是图论三件套DFS 一次全带走。优先选Kahn的场景只想要拓扑序别的信息一概不要——出队即收、顺序天然正确不用反转数据量很大、课程链很长——DFS 递归可能栈溢出Kahn 无递归天然安全起手想好讲——模拟排课还债比三色状态机更接近生活直觉。建议默认起手 Kahn好讲、无栈溢出但一定要把三色版也练熟——遇到染色类变体题它就是你的杀手锏。八、总结三题一张表三个直觉一句话8.1 三题总对比表题目难度问法判环/语义收集方式时间空间207中等能不能学完撞灰 / 排不完 环—O(V E)O(V E)210中等按什么顺序学同上DFS 后序[::-1]Kahn 出队即收O(V E)O(V E)1462中等u 是 v 的先修判环换成算可达DFS 染黑即算完Kahn 拓扑序传播O(V E) 每查询 O(1)O(V E)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判环换成算可达 → 位集布尔数组黑 已算完拓扑序传播 拓扑排序：用一套模板秒杀leetcode「课程表」系列三连题
LeetCode 207. 课程表 × 210. 课程表 II × 1462. 课程表 IV三题均为中等 DFS 三色标记 Kahn 双解法关键词拓扑排序 · DFS 三色标记 · Kahn · 位集 · LeetCode写在前面你在排课系统在防死锁假设你要给自己排一学期的课想学「机器学习」得先学「线性代数」想学「线性代数」得先学「微积分」想学「微积分」得先学「线性代数」……最后这条显然不合理没有一门课能先开始因为你永远等不到它的前置课。这就是依赖关系里的「死锁」计算机里叫环。LeetCode 的 207、210、1462问的都是这件事的变体题号难度问法本质207. 课程表中等能不能学完有没有环210. 课程表 II中等按什么顺序学输出拓扑序1462. 课程表 IV中等u 是不是 v 的先修有向可达传递闭包好消息是这三题共用一套模板。210 只是 207 的判环逻辑上多收集一行顺序1462 只是把判环换成算可达。本文给出两套模板DFS 三色标记和Kahn 入度 BFS你会一次会三题 × 两种思路。一、统一模板1.1 核心概念先修、入度、拓扑序先修关系[a, b]表示要学 a必须先学 ba 依赖 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约定如下graphdefaultdict(list)indeg[0]*numCoursesfora,binprerequisites:graph[b].append(a)# b 修完 → 解锁 a边 b → aindeg[a]1# a 的入度 a 还欠几门先修注意方向先修 → 后修即graph[b].append(a)207/210 的元组里 a 是后修、b 是先修。⚠️ 这是全篇第一个坑方向写反成graph[a].append(b)207 判环碰巧没事但 210 的输出顺序会整个颠倒。1.3 判环的两种判据同一张图两套方法各用各的判环方式方法判环依据一句话DFS 三色标记撞到灰 环递归栈上的祖先 灰绕回自己就是环Kahn 入度 BFS排不完 环环里的课互相欠债永远进不了队机制细节分别在第二、三章讲透先记住结论即可。1.4 三题 × 模板对应关系表题目难度问法模板用法DFS 三色版Kahn 版207中等能不能学完原样判环撞灰 环 → True/False排不完 环 →done n210中等按什么顺序学判环 收集染黑时order.append[::-1]出队即收 len n1462中等u 是 v 的先修判环 → 算可达位集黑 已算完向上合并拓扑序传播位集记住这张表的演进方向判环 → 判环 收集 → 判环换可达。后面四五六节就是按这个顺序逐个实战。二、方法一DFS 三色标记2.1 为什么是三色两种颜色不够吗先回答一个直觉问题判环用访问过 / 没访问过两个标记不就够了吗不够。因为 DFS 递归展开时一个节点其实有三种状态少一种就漏判环状态代码含义白0还没访问过灰1正在递归栈上当前探索路径上的祖先黑2已探索完确认安全为什么两种颜色不够假如只有访问过/没访问过当邻居 B 再次撞上 A 时你分不清两种完全相反的情况A 是正在栈上的祖先 → 你从 A 出发绕回了 A →环A 是早已安全的过去式 → 撞上它只是剪枝机会 →没事。举个最小例子numCourses 2先修[[1,0],[0,1]]——1 依赖 00 又依赖 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 就是模拟真实的排课流程找出所有入度 0的课先修全齐进队上一门课 u所有依赖 u 的课 v 的入度减一帮别人还债v 入度变成 0 → 解锁进队直到队空。为什么全上完就必然无环因为环里的课互相欠着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 黑出栈永久安全returnTruegraphdefaultdict(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:graphdefaultdict(list)indeg[0]*numCoursesfora,binprerequisites:graph[b].append(a)indeg[a]1queue[iforiinrange(numCourses)ifindeg[i]0]done0whilequeue:new_queue[]foruinqueue:done1# 每上一门课 1forvingraph[u]:indeg[v]-1ifindeg[v]0:new_queue.append(v)# 先修全齐 → 解锁queuenew_queuereturndonenumCourses# 全上完 无环复杂度时间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 的改动每个版本只多两行版本改①改②DFS 三色染黑时order.append(u)后序收集有环return []最后return order[::-1]Kahn出队时order.append(u)return order if len(order) numCourses else []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)# ① 后序收集returnTruegraphdefaultdict(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]:graphdefaultdict(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)queuenew_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 ≤ 100queries ≤ 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 就是 TruefromcollectionsimportdefaultdictclassSolution:defcheckIfPrerequisite(self,numCourses:int,prerequisites:list[list[int]],queries:list[list[int]])-list[bool]:graphdefaultdict(list)fora,binprerequisites:graph[a].append(b)# 先修 → 后修正向边ans[]foru,vinqueries:seen{u}stack[u]foundFalsewhilestackandnotfound:xstack.pop()foryingraph[x]:ifyv:foundTruebreakifynotinseen: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)|(1p)# 先修 p 和 p 的先修都是 u 的先修color[u]2# 灰 → 黑returnreach[u]graphdefaultdict(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]:graphdefaultdict(list)indeg[0]*numCoursesfora,binprerequisites:graph[a].append(b)# 1462a 先修 → b 后修正向边拓扑排序用indeg[b]1queue[iforiinrange(numCourses)ifindeg[i]0]reach[0]*numCourseswhilequeue:new_queue[]foruinqueue:forvingraph[u]:reach[v]|reach[u]|(1u)# u 和 u 的全部先修都成了 v 的先修indeg[v]-1ifindeg[v]0:new_queue.append(v)queuenew_queuereturn[bool((reach[v]u)1)foru,vinqueries]复杂度时间O(V E) 每查询O(1)空间O(V E)。6.5 位集为什么这么香朴素版逐查询 DFS模板版位集预处理无O(V E) 一遍搞定单个查询O(V E) 重跑一次O(1)一个移位 一个与运算Q 10⁴ 总开销≈ 5 × 10⁷≈ 5 × 10³ 10⁴numCourses ≤ 1001 u一个位一门课Python 大整数天然就是位集零额外成本。本节注意点判环逻辑可省题目保证无环“撞灰 环”排不完 环都不会触发但三色版的灰判断建议保留——它和模板同构万一题目条件变化也不会栈溢出方向别弄混DFS 版存先修列表graph[b].append(a)Kahn 版存正向边graph[a].append(b)两个版本用途不同各写各的原因见 6.4 注释。七、方法对比怎么选DFS 三色标记Kahn入度 BFS核心染灰染黑抓环模拟排课还债判环依据撞到灰 环排不完 环210 收集后序 [::-1]出队即收递归深度可能栈溢出课程链很长时无递归天然安全可读性稍绕要理解三色直观生活类比通用性好判环、染色、后序802 同源中只能剥洋葱信息量少什么时候用三色什么时候用 Kahn优先选三色 DFS的三种场景题目不止问能不能排还问谁安全 / 环在哪——比如姊妹题 802. 找到最终安全状态黑 安全直接就是答案DFS 染完色结果就出来了Kahn 还得绕需要 DFS 后序 / 深度这类信息——后序天然是子孙在前、自己靠后配合反转就是拓扑序一鱼两吃你想复用同一套模板刷其他图论题——判环 染色 后序是图论三件套DFS 一次全带走。优先选Kahn的场景只想要拓扑序别的信息一概不要——出队即收、顺序天然正确不用反转数据量很大、课程链很长——DFS 递归可能栈溢出Kahn 无递归天然安全起手想好讲——模拟排课还债比三色状态机更接近生活直觉。建议默认起手 Kahn好讲、无栈溢出但一定要把三色版也练熟——遇到染色类变体题它就是你的杀手锏。八、总结三题一张表三个直觉一句话8.1 三题总对比表题目难度问法判环/语义收集方式时间空间207中等能不能学完撞灰 / 排不完 环—O(V E)O(V E)210中等按什么顺序学同上DFS 后序[::-1]Kahn 出队即收O(V E)O(V E)1462中等u 是 v 的先修判环换成算可达DFS 染黑即算完Kahn 拓扑序传播O(V E) 每查询 O(1)O(V E)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判环换成算可达 → 位集布尔数组黑 已算完拓扑序传播