☰
LeetCode 207课程表题解:拓扑排序与有向图环检测
2026/10/11 5:45:27 网站建设 项目流程

如果你大学选课经历过“这门课必须先修那门课,那门课又必须先修这门课”的循环,你会懂什么叫绝望。LeetCode热题100里的课程表(207 Course Schedule)考的就是这个场景:给出一共要修多少门课,以及每门课的前置课程列表,问你能不能找到一种上课顺序把课全部修完。表面上是教务系统需求,本质上是一个经典图论问题——判断一个有向图是否存在环。这篇文章我会从题目建模讲到两种主流解法(BFS拓扑排序和三色DFS),再把建图方向、孤立节点、自环这些真实踩过的坑一并写出来。它适合正在刷LeetCode热题100的读者,也适合刚开始接触图论拓扑排序、想一次性把原理和模板都搞清楚的人。

1. 读懂题目:从“上课顺序”到“有向图环检测”

1.1 题目原文与两个必须秒懂的例子

在LeetCode上,课程表这道题的描述很直白。它会给你一个整数numCourses表示总课程数,课程编号从 0 到numCourses - 1;再给你一个二维数组prerequisites,其中每一项prerequisites[i] = [ai, bi]表示:想要学习课程ai,必须先完成课程bi。最后要求返回true或false,判断你能不能找到一种上课顺序把所有课全部修完。

这里最容易看走眼的就是[ai, bi]的先后:ai是要学的课,bi是前置课。所以当你在图上画边的时候,方向应该是bi -> ai,也就是说先修课指向后续课。我见过不少第一次写这道题的人把边方向存反,后面所有逻辑都跟着乱掉。

两个示例就能把题意说清楚。第一个:numCourses = 2,prerequisites = [[1, 0]]。意思是课1要先修课0,那么上课顺序就是0 -> 1,能学完,返回true。第二个:numCourses = 2,prerequisites = [[1, 0], [0, 1]]。课1要先修0,课0又先修1,两个课互相等对方,谁也排不到前面,返回false。很多人在第二个例子才反应过来:这不是排课表,这是判断图中能不能出现一个“死循环”。

1.2 把课程建模成有向图的三个关键选择

一旦想到用图,建模其实非常固定,但有几个选择值得先想清楚。

第一个选择是顶点。每个课程编号天然就是一个顶点,numCourses就是顶点总数V,不用额外映射。第二个选择是边。prerequisites里每一项都是一条有向边,从先修课指向后续课。这里有一个本质问题:题目要判断的是“能不能把课程按某种线性顺序排出来”,在有向图里这就是“是否存在拓扑排序”。而有向图存在拓扑排序的充要条件就是图无环。第三个选择是存储结构。绝大多数时候用邻接表,因为课程之间的先修关系通常是稀疏的,用邻接表存边只花O(E)的空间,遍历每个节点的后继也快;邻接矩阵虽然写起来直观,但要O(V^2)空间,在numCourses到几千上万的时候非常浪费。

你可以把有向图里的环理解成一条环形管道:课程依赖沿着管道转圈,你从任何一个入口进去,最终都会绕回自己。环上的每一门课都要求“环上另一门课先上”,这在自己和自己互相拉扯,不可能有排课顺序。所以这道题从建模完成的那一刻起,就变成了一个纯粹的图论问题:给定一个有向图,判断它是否包含环。

1.3 三个常见的错误方向

我第一次刷这道题时,第一反应不是拓扑排序,而是并查集。这是个很自然的直觉,因为“两个课程能不能同时修”“哪些课是一组的”听起来很像连通性问题。但并查集解决的是无向图的连通分量,它不记录边的方向。比如[1,0]和[0,1]这两种完全相反的依赖,在并查集里都会被合并成同一个集合,你根本判断不出它们是不是环形依赖。所以并查集方向错了。

第二个错误方向是只用布尔数组visited做DFS。如果某个节点已经被访问过,就立刻认为有环,这是不对的。因为有向图里完全可能存在两条不同路径汇聚到同一个节点,A -> B 和 A -> C -> B。从A走第一条路访问了B,再从C走到B时,B确实访问过了,但这两条路不构成环。真正需要标记的是“当前这条递归路径上是否重新遇到了自己”,这就是后面要说的三色标记法。

第三个错误方向是拿到题就上邻接矩阵加暴力深搜。对于numCourses只有几十的测试用例能过,但LeetCode上数据规模一大,O(V^2)的空间和O(V^2)的遍历时间都会让代码又慢又占内存。正确做法是邻接表加拓扑排序或三色DFS,复杂度稳定在O(V+E)。

2. BFS解法先上:入度为零的课先修(Kahn算法)

2.1 “剥洋葱”思想:为什么入度为零的课可以安全先修

我建议先掌握BFS版本的拓扑排序,也就是Kahn算法,因为它的过程和“排课表”的人类直觉完全一致。你想想自己选课:第一学期能选的课是哪几门?是没有先修要求的课。在图上,没有先修要求的课就是“入度为0”的节点,也就是没有任何边指向它的顶点。

Kahn算法的核心就一句:反复把当前图中入度为0的节点加入队列并弹出,每弹出一个节点,就把它所有“出边”删掉,等价于这门课修完了,它后面那些课的先修条件少了一项,也就是后继节点的入度减1。某个后继节点的入度减到0,说明它的所有先修课都已修完,可以成为下一批可修课程。

为什么能保证这样剥到最后一定正确?有一个关键性质:任何有向无环图都至少存在一个入度为0的节点。反过来说,如果一张图里每个节点的入度都大于等于1,那你沿着任意一条入边不断回溯,由于节点数量有限,必然会在某个位置绕回自己,也就是存在环。所以“剥洋葱”的过程能一直进行下去,当且仅当图无环;如果最后队列提前空了,剩下的节点就是互相依赖的环。

提示:Kahn算法的删除是“逻辑删除”,不需要真的从邻接表里删边,只需要维护入度数组,让每个后继节点的入度减1。代码写起来非常轻。

2.2 Python实现:邻接表、入度表、队列三件套

下面是标准写法,可以直接在LeetCode 207跑通:

from collections import deque from typing import List class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # 1. 建图:邻接表 + 入度表 adj = [[] for _ in range(numCourses)] indegree = [0] * numCourses for a, b in prerequisites: adj[b].append(a) # b 是 a 的先修课:边 b -> a indegree[a] += 1 # a 多了一个先修条件 # 2. 初始入队:所有没有先修课的课程 q = deque([i for i in range(numCourses) if indegree[i] == 0]) count = 0 # 3. 逐层剥除 while q: cur = q.popleft() count += 1 for nxt in adj[cur]: indegree[nxt] -= 1 if indegree[nxt] == 0: q.append(nxt) return count == numCourses

这段代码有几个细节值得展开。建图时为什么是adj[b].append(a)而不是反过来?因为后面的遍历要模拟“修完先修课,解锁后续课”,从先修课出发访问它的后继是最自然的。入度表则是用来统计每门课还差多少个先修课,indegree[a] += 1就是在给课程a挂一个“待解锁”标记。

初始化队列用了一个列表推导,把indegree为0的课程全部放进去。注意队列里一开始就可能有多个课程,这完全正常,因为可能有好几门课都没有先修要求。后面每次popleft,都代表这门课可以被安排到现在的位置;count统计的正是已经安排出的课程数量。

遍历出边做indegree[nxt] -= 1时,为什么可以放心大胆地减?因为节点cur已经出队,它在nxt的那项先修条件已经满足,之后不可能再用到cur。如果减完nxt的入度变成0,说明nxt所有先修课都在当前已修序列里,可以入队。

注意:如果最后count等于numCourses,说明每门课都被安排上了,返回true;如果入队计数不足,说明有环,返回false。这个判断就是整道题的答案。

2.3 手动推演两个用例:无环剥到空,有环剥不动

只看代码不推演,遇到稍微复杂一点的用例还是容易发虚。我拿两个例子带你走一遍。

第一个是无环的例子:numCourses = 5,prerequisites = [[1,0],[2,0],[3,1],[4,2],[4,3]]。先修关系是0 -> 1、0 -> 2、1 -> 3、2 -> 4、3 -> 4。初始入度分别为[0,1,1,1,2],队列[0]。

弹出0时,后继是1和2,它们的入度从1减到0,队列变成[1,2]。弹出1,后继3的入度从1减到0,入队,队列[2,3]。弹出2,后继4的入度从2减到1,不入队,队列[3]。弹出3,后继4的入度从1减到0,入队,队列[4]。最后弹出4,count = 5,返回true。

第二个是有环的例子:numCourses = 5,prerequisites = [[1,0],[2,1],[3,1],[4,3],[1,4]]。这里有环1 -> 3 -> 4 -> 1。初始入度是0:0, 1:2, 2:1, 3:1, 4:1,队列[0]。弹出0后,1的入度从2减到1,队列立刻空了,count = 1,剩下1、2、3、4全都进不了队列。为什么会这样?因为环1 -> 3 -> 4 -> 1里的每个节点都至少有环内部的一条入边,剥掉0这个外部节点后,环上的节点入度仍然至少为1,谁也无法先修,课程自然修不完。

这个推演过程建议你自己在纸上画一遍,尤其是第二个例子,它会让你真正理解“环上的节点永远入度不小于1”这句话。

3. DFS解法:三色标记,路径上撞见自己就是环

3.1 为什么布尔visited在这个问题上不够用

BFS能够解决,但很多面试官会继续追问DFS版本,或者你自己也想写出更短的代码。DFS检测有向环的关键在于:不是检测“节点是否被访问过”,而是检测“在当前的递归路径上,是否再次访问到了自己”。这一点和普通DFS判重有着本质区别。

如果用单一的布尔数组,第一次进入B时标记visited[B] = True,之后从另一条路径再次进入B,你会发现它已经被访问过,很容易误判为“发现环”。但这不是环,两条路径可能只是在前缀分流后又汇聚,并没有形成回路。比如0 -> 1、0 -> 2 -> 1,1被两条路径到达,但全图无环。

真正能判断环的是递归调用栈。当我们沿0 -> 1 -> 2一路递归时,调用栈里有0、1、2这些节点;如果此时某个节点有一条出边直接指向当前栈里的某个节点,比如2 -> 0,那就说明存在一条从0出发绕一圈又回到0的路径,这必然构成环。因此,节点需要分成三种状态:未访问、正在当前递归栈中、已经递归完毕无环。这就是三色标记法。

3.2 三色DFS的完整写法

用一个state数组,0表示未访问,1表示正在递归栈中,2表示已经递归结束且确认无环。代码如下:

from typing import List class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: adj = [[] for _ in range(numCourses)] for a, b in prerequisites: adj[b].append(a) state = [0] * numCourses def dfs(u: int) -> bool: if state[u] == 1: return False # 当前递归路径上又遇到 u,找到环 if state[u] == 2: return True # 这个节点之前已经确认无环,跳过 state[u] = 1 for v in adj[u]: if not dfs(v): return False state[u] = 2 return True for i in range(numCourses): if state[i] == 0 and not dfs(i): return False return True

这段代码的顺序不要乱。进入函数后先做两个提前返回:遇到状态1直接说明遇到递归栈中的节点,有环;遇到状态2说明以这个节点为起点的整棵子树都已经检查过,并且没发现环,直接返回True可以避免重复劳动。然后把当前节点标记为状态1,递归遍历它的所有后继。如果所有后继都没问题,最后把状态置为2再返回。

主循环里的for i in range(numCourses)经常被漏掉。图不一定是连通的,可能存在几门课既不依赖别人,也没有别人依赖它们。如果只从0号课程开始DFS,孤立节点永远不会被检查,你可能会漏掉独立成环的某个子图。虽然从0出发的遍历返回了True,但其他连通分量里藏着一个环,最后答案就错了。

提示:这道题中如果prerequisites里出现[0,0]这种自环,DFS会在dfs(0)的 for 循环里再次调用dfs(0),此时state[0] == 1,直接返回False。自环也是一种环,必须判错。

3.3 递归栈的可视化:环是如何被“回头路”发现的

我还想更直观地展示一下DFS的判环过程。沿用之前那个有环例子:numCourses = 5,先修边为0 -> 1、1 -> 2、1 -> 3、3 -> 4、4 -> 1。实际存在的环是1 -> 3 -> 4 -> 1。

主循环从0开始,先调用dfs(0)。0的状态变成1,遍历到后继1,于是dfs(1)。1的状态变成1,它有两个后继2和3。先进入dfs(2),2没有后继,正常返回,状态变成2。接着进入dfs(3),3的状态变成1,遍历到后继4,进入dfs(4)。4的状态变成1,遍历到后继1,此时关键瞬间来了:调用dfs(1),发现state[1] == 1。

这里的状态1意味着什么?意味着节点1还在当前递归栈的最底层,还没有执行完毕。现在从4的路径出发又回到了1,说明沿着1 -> 3 -> 4 -> 1这条有向边走了一圈,回来了。于是dfs(1)返回False,这个False会顺着递归一层层传回给4、3、1、0,整棵树判断失败。

可以这样记忆:只要在遍历邻接点时,发现某个邻居正好处于状态1,就等价于发现一条从当前路径某个祖先节点出发、绕了一圈又回到祖先的回路。状态2则不会触发这个判断,因为它表示那个节点已经“功成身退”,不在当前路径上,即使再次遇到也只是不同分支汇聚,不是环。

4. 两种解法怎么选:正确性论证与复杂度对比

4.1 “出队数量等于课程数”为什么能当作无环的充要条件

很多人学完Kahn算法后只是背了代码,并不清楚为什么count == numCourses就能断定无环。这里把逻辑补完整。

先看必要性:如果一个有向图存在环,环上的每个节点都有至少一条来自环内其他节点的入边。Kahn算法只会把入度为0的节点弹出,外部节点被剥掉后,环内节点来自环内的入边永远不会消失,所以环上任何节点都不可能入队。因此最终出队数量一定小于顶点总数。课程表这道题里,出现这种情况就说明有课永远排不上,返回false。

再看充分性:如果算法成功让所有节点都出队了,那说明整个过程没有遇到“卡住”的情况。每次弹出的节点在弹出时入度为0,它的所有先修条件都已经由之前弹出的节点满足。把出队顺序作为修课顺序,每一门课都合法,这就是一个完整的拓扑排序。存在拓扑排序的有向图一定是无环图,因为如果有环,环中的节点不可能在序列里分出先后,总会有人需要在依赖自己的人之后出现。

从归纳的角度看更简洁:无环图至少有一个入度为0的节点,把它弹掉之后,剩下的子图依然无环;反复执行,所有节点都能弹出。反向则做不到。所以count == numCourses不只是一个巧合,它等价于图的拓扑排序存在,等价于图无环。理解了这一层,你在面试里被追问“为什么”的时候才不会卡壳。

4.2 时空开销:为什么两种解法都是O(V+E)

这道题的规模通常用顶点数V和边数E描述,两种解法的理论复杂度都是O(V+E),但实际常数和风险不一样。我用表格列一下。

对比维度BFS / KahnDFS 三色
建图开销O(V+E)O(V+E)
主过程复杂度O(V+E)O(V+E)
额外空间邻接表O(V+E) + 队列O(V) + 入度O(V)邻接表O(V+E) + 状态数组O(V) + 递归栈O(V)
是否天然得到拓扑序出队顺序就是需要后序压栈再逆序
递归栈溢出风险无链式依赖有风险
写错的可能性方向容易写反,但逻辑直白状态判断顺序容易漏

为什么一定是O(V+E)而不是更高?因为建邻接表时每条边被处理一次;BFS中每个顶点入队出队各一次,每条边作为某个顶点的出边被访问一次;DFS中每个顶点状态最多从0变成1再变成2,每条边同样被遍历一次。所以无论遍历还是建图,都是线性的。

如果你不建邻接表,而是在每个节点都用for扫描prerequisites找后继,复杂度会变成O(V*E),数据规模稍微大一点就直接超时。这个优化思路和图本身一样重要:先花O(E)建表,换得所有访问都只和V+E相关,这笔买卖非常划算。

4.3 面试现场怎么选择:先问清“要不要输出顺序”

如果你是笔试,能跑通最重要,我一般建议用BFS,因为代码直白、不易错、不用考虑递归栈。但如果是面试,情况会有变化。

面试官问你“判断能否完成所有课程”时,两种都能说。我倾向先说BFS,因为Kahn算法本身就是拓扑排序,讲到后半段可以顺势引出拓扑序的实际应用场景。但如果面试官追问“如果不判断布尔结果,而是让你输出一种合法的上课顺序怎么办”,BFS依然是最顺的,因为队列弹出顺序就是答案。

DFS版本适合用来展示你对递归状态的理解。你可以主动提到三色标记法、递归栈、状态2的剪枝作用,这些都会给面试官留下“这个人真的理解图遍历”的印象。不过要小心极端情况:如果课程数量特别大,比如10万门课连成一条链,DFS递归深度会非常深,Python或Java默认栈可能溢出。这时候你主动说“我会改用BFS迭代版本,避免系统栈溢出”,反而加分。

另外可以问面试官一个问题:要求输出顺序是否必须字典序最小?如果必须,BFS的普通队列要换成优先队列;如果不要求,普通队列即可。这种追问能够体现你不仅会做题,还知道需求变化对算法选型的影响。

5. 高频变体:从课程表到课程表II

5.1 课程表II:把布尔答案升级成具体修课顺序

LeetCode 210《课程表 II》是207的亲兄弟,输入完全一样,只是要求返回一种合法的课程修读顺序,如果不可能完成就返回空数组。它的解法就是把207的BFS稍微改一下:出队时不再只是count += 1,而是把课程追加进结果数组;最后如果结果数组长度等于numCourses,返回结果,否则返回空数组。

完整代码如下:

from collections import deque from typing import List class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: adj = [[] for _ in range(numCourses)] indegree = [0] * numCourses for a, b in prerequisites: adj[b].append(a) indegree[a] += 1 q = deque([i for i in range(numCourses) if indegree[i] == 0]) res = [] while q: cur = q.popleft() res.append(cur) for nxt in adj[cur]: indegree[nxt] -= 1 if indegree[nxt] == 0: q.append(nxt) return res if len(res) == numCourses else []

老实说,这道题的代码比207还少一行,但面试价值反而更高,因为它逼你输出一个“真实可执行的顺序”,光知道有没有环还不够。我遇到过不止一次的场景:候选人能把canFinish背出来,但让他输出具体顺序时就卡住,因为他不理解BFS出队顺序本身就是拓扑序。如果你把207和210连在一起刷,这部分会很自然地打通。

提示:如果题目要求任意合法顺序,那么BFS弹出哪门课都可以,只要满足先修关系。LeetCode只校验是否正确,不要求字典序,所以普通队列就够了。

5.2 变体:字典序最小的修读顺序

有些进阶题会在课程表II基础上加一个条件:如果有多种合法顺序,输出字典序最小的一种。这时候普通队列就不够了,因为popleft只会取出最早入队的节点,而不会考虑编号大小。需要改用最小堆,每次从所有入度为0的课程里挑编号最小的那个先修。

给一个简化的实现思路:

import heapq from typing import List def findOrderLexicographically(numCourses: int, prerequisites: List[List[int]]) -> List[int]: adj = [[] for _ in range(numCourses)] indegree = [0] * numCourses for a, b in prerequisites: adj[b].append(a) indegree[a] += 1 heap = [i for i in range(numCourses) if indegree[i] == 0] heapq.heapify(heap) res = [] while heap: cur = heapq.heappop(heap) res.append(cur) for nxt in adj[cur]: indegree[nxt] -= 1 if indegree[nxt] == 0: heapq.heappush(heap, nxt) return res if len(res) == numCourses else []

为什么不能用“把最终结果排序”的方式实现字典序?因为合法的修课顺序不是孤立序列,它受依赖关系约束;如果先随便生成一个拓扑序再排序,很可能破坏前置关系。最小堆才是标准做法:每一步都在“当前所有没先修课可上”的集合里取最小,这正好符合字典序贪心。

5.3 工程场景里到处都是这个模型

学完这道题,不要只把它当成面试题。你先修课模型在所有依赖解析系统里都能看到。

包管理器解析依赖是最典型的例子。npm install或者pip install在安装前会构建依赖图,如果出现循环依赖,包管理器必须检测出来并报错,否则无法确定安装顺序。编译器里的头文件/模块依赖、构建工具里的任务依赖,本质上也是同一个拓扑排序问题。还有分布式计算框架里,任务被组织成有向无环图DAG,一个stage依赖前一个stage的输出,调度器必须保证依赖执行完毕再启动后续任务,一旦出现环就要告警。换句话说,课程表这道题的解法,就是你以后写依赖解析代码时的第一版原型。

面试里如果聊到这些场景,你可以主动提一句“这道题就是DAG上的拓扑排序,核心是检测有没有环”,会让你的回答更有工程感,而不只是“我会写算法题”。

6. 复盘与踩坑:这些细节决定你能不能AC

6.1 边方向写反:最经典的翻车点

我最想强调的还是建图方向。prerequisites[i] = [ai, bi]表示上ai前必须先上bi,因此邻接表存法是adj[bi].append(ai)。如果你是先看的课程表II,可能见过有人存成adj[ai].append(bi),还配了相反的入度更新,那套思路在同一道题里其实也能自洽,因为它是把依赖关系反过来建模。但LeetCode 207的标准建模是“先修课指向后续课”,两种写法不能混用。

怎么自测方向有没有写对?最简单的办法是用题目给的第一个示例[[1,0]]跑一遍,正确结果应为true。如果得到的答案是false,优先怀疑建图方向。另一个检查方法是:入度为0的课程应该在没有先修课的课程集合里,如果你发现答案里最先可修的课反而出现在很多课程之后,方向大概率反了。

提示:我建议你在代码里加一行注释# 边:先修课 b -> 课程 a。刷题时这行注释能省下大量排查时间。

6.2 DFS主循环漏掉孤立节点

DFS版本有一个隐蔽的bug:主循环只从dfs(0)开始,然后相信返回值。如果图里存在一个和0号课程完全不连通的环,比如numCourses = 4,prerequisites = [[2,3],[3,2]],课0和课1都是孤立的,从0开始DFS无论如何也走不到2和3那组依赖环。最后可能错误地返回true。

解决办法就是for i in range(numCourses),对每个state[i] == 0的节点都发起一次DFS。你不能假设课程编号0的节点一定和其他所有节点连通,这正是“有向图不一定强连通”在题目里的体现。BFS版本为什么天然安全?因为初始队列会收集所有入度为0的节点,包括孤立节点,它们一上来就入队了。

每次写完DFS版,我习惯专门用一个独立环用例做冒烟测试,比如上面那个[[2,3],[3,2]],保证它能返回false。这种边界测试比random大样例更能发现漏遍历的问题。

6.3 自环、重复边这些边界输入别忽视

边界输入往往比正常用例更容易暴露问题。自环是第一种:prerequisites里出现[i, i],也就是一门课的先修课是自己。这显然不可能完成。BFS下,节点i的入度因为自己指向自己而变成1,它永远不会进入初始队列;它的入队机会依赖队列里的某个节点把它减到0,但没有任何外部队列节点能让它减到0,所以最后count必然不足。DFS下,dfs(i)遍历邻居时再次调用dfs(i),状态是1,直接返回false。两种解法都能正确识别,只是路径不同。

重复边是第二种。题目通常不会给重复的先修关系,但如果你在本地测试时遇到类似[[1,0],[1,0]],要注意BFS的入度会被重复加两次,出队时也会重复减两次,最终计数依然是正确的,不影响结果。真正的危险不在重复边本身,而在某些选手为了“去重”给邻接表加set,结果不小心把入度和邻接表逻辑改出不匹配。

第三种边界是图中有多条独立链,比如numCourses = 3,prerequisites = []。没有先修关系时,三节课都直接入队,BFS会把它们全部弹出并返回true。很多人忘记考虑prerequisites为空的情况,这个边界同样要求你能正确处理入度为0的大批节点。

6.4 性能隐患:不建邻接表,边查边找会超时

最后一个坑来自性能。有些初学者在DFS版本里不建邻接表,而是每访问一个节点就用for a, b in prerequisites扫描一遍原始数组,判断b是否等于当前节点,再继续递归。这样的写法功能上没错,但每次访问节点都要扫整个数组,整体复杂度变成O(V*E)。在numCourses = 2000、prerequisites接近上万条时,这个复杂度已经明显卡顿,LeetCode上很容易超时。

所以要养成一个习惯:任何图论题,第一步先把邻接表建好。不管是207还是其他图题,邻接表建完,后面所有遍历都能以O(V+E)完成。本题如果用defaultdict(list)也可以,但既然课程编号严格从0开始且连续,直接用List[List[int]]初始化numCourses个空列表最快,既省去哈希开销,代码也更好读。

最后分享一点个人经验。LeetCode热题100里的图论题数量并不多,课程表属于性价比最高的一道,因为它在一次提交里把“语义建模、图算法选型、边界处理、复杂度分析”全部练到了。我把BFS版和DFS版各写了五遍以上,直到闭着眼都能写对adj[b].append(a)的方向。如果你也准备刷热题100,建议把207和210连着做,先用BFS把模板敲熟,再用三色DFS把原理吃透。之后你再看任何一份课程表题解,都会觉得思路清爽,不会再被复杂度或者细节绕晕。

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询