1. 专题5在整个图论体系里的位置先交代一下背景day52代码随想录算法训练营刷到图论专题5。前面几十天把数组、链表、哈希、二叉树、回溯、贪心、动态规划基本过了一遍图论是从day48左右才开始的。前四个专题分别把图论基础、深度优先搜索、广度优先搜索、并查集和几个岛屿题目讲透了到了专题5刷题群里明显话少了一半——不是因为大家不努力而是这天的内容真的开始“硬”了。1.1 前四个专题到底学了什么跳进专题5之前最好先知道自己手上已经有什么牌。专题1是图论基础什么是图、什么是度、有向无向、邻接矩阵和邻接表怎么选这些理论以前上课都听过但真正动手建图是另一回事。专题2和专题3基本被DFS和BFS包场了从岛屿数量这种flood fill题入手再到岛屿周长、岛屿最大面积、飞地的数量本质上是把二维矩阵当图来遍历。专题4重点讲并查集判断两个节点是否连通、合并两个集合最经典的题目是省份数量、冗余连接这类题用并查集是真的省心。这四个专题刷完最直观的感受是图论题大部分时候是在“遍历”只要模板背得熟变形题也能应对。但专题5不一样它不再满足于让你从A走到B而是要你回答“这张图整体上长什么样”“有没有闭环结构”“能不能一笔画完”“相距最远的两个点有多远”。这类问题需要更多全局视角也是面试里区分“会刷模板”和“真懂图论”的分水岭。1.2 专题5为什么突然变难了难度上升最直接的原因是前四天还能靠“把图当成一棵多叉树的遍历”来混到了专题5你会发现图比树麻烦得多。树有根、有层次、没有环递归回去不会迷路图有环、有横跨边、有重边、有孤立点一个状态可能从多个方向被访问光是判重就要多想一步。另一个难点在于“模型转换”。专题5的很多题表面上看根本不是图比如一张机票列表、一场课程依赖关系、一个集群里的网络连接。你得自己把这些实际场景翻译成节点和边再套对应的算法。这一步对大多数人来说是陌生的遇到题第一反应是“这也能用图做”而不是“这属于图的什么结构”。我身边很多同学是到这一天开始放弃的觉得图论全靠天赋。其实不是天赋问题是方法没换——遍历图你可以靠记忆背模板但分析图的全局性质必须靠理解原理。1.3 这一期专题5我主要复盘的三条主线不同期训练营的内容推进会有微调我这期刷到的专题5核心落在了三块强连通分量与Tarjan、欧拉路径与Hierholzer、图的直径计算。前两个是“从图里提取特殊结构”第三个是“量化图的两端距离”两两之间既有区别又有联系都是进阶图论中特别容易在笔试和面试中出现的点。这篇文章不打算照抄当天课程的题解顺序而是把三条主线拆开每个方向讲清楚原理是什么、模板怎么写、题怎么套、容易踩哪些坑。已经刷完的人可以当作复习和对照还没刷到的人建议先收藏等推进到专题5再回来看。2. 三个核心算法的原理与实现模板2.1 强连通分量与Tarjan把有向图压缩成DAG先说什么叫强连通分量。在有向图里如果两个节点能互相到达那么它们属于同一个强连通分量。把每个强连通分量缩成一个点原来的有向图就变成一个有向无环图也就是DAG。为什么要做这一步因为DAG好处理拓扑排序、DP都能用而带环的有向图很难直接做这些事。很多难题的第一步都是缩点缩完才发现是道送分题。Tarjan算法的核心是个DFS过程需要维护三个东西dfn数组记录每个节点第一次被访问的时间戳low数组记录这个节点能追溯到的最早时间戳还有一个栈记录当前DFS路径上还没确定归属的节点。每次遍历到邻接节点v如果v还没访问过就递归然后更新low[u] min(low[u], low[v])如果v在栈里说明找到了回边就更新low[u] min(low[u], dfn[v])。模板我习惯写成这样稳一点别省变量#include bits/stdc.h using namespace std; const int MAXN 10005; vectorint g[MAXN]; int dfn[MAXN], low[MAXN], inStack[MAXN], idx 0; stackint st; vectorvectorint sccs; void tarjan(int u) { dfn[u] low[u] idx; st.push(u); inStack[u] 1; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (inStack[v]) { low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { vectorint comp; while (true) { int x st.top(); st.pop(); inStack[x] 0; comp.push_back(x); if (x u) break; } sccs.push_back(comp); } }关键逻辑在最后当 low[u] dfn[u]说明u是某个强连通分量里时间戳最小的那个也就是这个分量的“根”这时候把栈顶一路弹出到u栈里这些东西就是一个完整的强连通分量。理解这一点之后整个算法就通了。用生活场景类比的话就像一群人按“谁先入场”编号如果发现某个人的编号等于它能追溯到的最小编号那它就是这个圈子的发起人圈子里垫后进来的所有人都归它管。这个算法的复杂度是O(VE)一遍DFS解决实际刷题时可以在1秒内跑完十万级别的图。2.2 欧拉路径一笔画问题的判定与构造欧拉路径的概念其实小学就接触过“一笔画”。一个图如果存在一条路径经过每条边恰好一次这条路径就是欧拉路径如果起点和终点相同就是欧拉回路。判定条件必须背清楚无向图存在欧拉通路奇度顶点的个数是0或2。0个奇度点是回路2个奇度点是通路起点和终点就是这两个奇度点。有向图存在欧拉通路最多一个点出度-入度1起点最多一个点入度-出度1终点其余所有点入度等于出度且把所有有向边看成无向边后整个图是连通的。构造欧拉路径常用Hierholzer算法通俗点说就是“先走支路最后走死胡同”。实现上有个特别重要的细节递归进入下一个节点之前必须先删掉这条边否则图里有环时你会无限循环。然后是在回溯之后再把当前节点加入结果不是进入节点时就加。为什么因为欧拉路径的本质是“能拖到最后走的边先不急着走”DFS一路闯到死胡同时那个节点反而是路径里靠后的部分。所以很多模板最后会输出反转后的序列。void dfs(int u) { // 以邻接表vector为例已按字典序或自定义优先级排好 while (!adj[u].empty()) { int v adj[u].back(); adj[u].pop_back(); // 先删边再递归 dfs(v); } ans.push_back(u); // 回溯后才push } reverse(ans.begin(), ans.end()); // 最终得到正确顺序我最早写这个模板时犯过一个错误先把节点push了再删边递归结果输出顺序完全是乱的。后来手动模拟了个小图才明白逆序插入是故意的——DFS往回“收线”的顺序正是一笔画从起点走到终点的镜像。2.3 图的直径从双BFS到多源最短路“图的直径怎么算”是很多刷图论的人会搜的问题它说的是一张图里距离最远的两个节点之间的距离。如果是无权图最常见的做法是双BFS。但注意这个做法严格来说只适用于树或所有边权相同的图并不适用于所有图。原理很简单从任意节点出发BFS记录最远节点A再从A出发做一次BFS记录最远节点BAB之间的距离就是直径。为什么在树中成立因为树没有环从A到最远点的路径一定会经过树的“腰”第二遍BFS自然能把直径的两端都找出来。但有环的图就不行了比如一个菱形图从某个节点BFS找到的最远点可能是错的起点导致第二遍结果不是真正的直径。这个陷阱面试时经常被拿来问答题时一定要说清楚前提。如果给的是带权图且权值非负直径通常要通过Floyd或Dijkstra来算。Floyd能求全源最短路然后取所有dist[i][j]的最大值即可但复杂度O(V^3)只适合小图。稀疏大图更合适的方案是每个节点都跑一次Dijkstra复杂度O(V * E log V)或者转换为最长路问题单独分析。实际比赛里图的直径题目通常不会让你拿Floyd硬跑几十万节点能跑的都是小数据。双BFS求树直径的核心代码很简单int bfs(int s, int far) { vectorint dist(n, -1); queueint q; dist[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); far u; for (int v : g[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } return dist[far]; } int diameter() { int a 0, b 0; bfs(0, a); // 第一次找最远点 int d bfs(a, b); // 第二次得到直径长度 return d; }3. 经典题目实操复盘3.1 力扣1192/变体用Tarjan找桥专题5里我刷到一道和力扣1192“查找集群内的关键连接”同源的题考的是无向图中的桥也叫割边。一条边是桥当且仅当删掉它之后连通分量的数量增加。经典的Tarjan求桥模板和求强连通分量很像但因为是无向图处理逻辑略有差异。核心判断条件是一条回边 v 指向已访问节点时low[u] min(low[u], dfn[v])而当递归完子节点v后如果low[v] dfn[u]说明v那边没有任何一条回边能绕到u或u之前那么u-v就是桥。这里有个特别容易踩的坑判断“跳过父边”时不能直接比较父节点要靠边的编号判断尤其在存在重边的情况下。如果只跳过父节点遇到两条平行的重边时第二条边会被当成回边从而错误地判断不是桥但实际两条重边中的任意一条删掉整个图依然是连通的这恰恰说明有重边时不应该把那条边当桥。看下面的模板怎么按边编号跳过void tarjanBridge(int u, int parentEdge) { dfn[u] low[u] idx; for (auto [v, eid] : g[u]) { if (eid parentEdge) continue; if (!dfn[v]) { tarjanBridge(v, eid); low[u] min(low[u], low[v]); if (low[v] dfn[u]) { // u-v 是一条桥 } } else { low[u] min(low[u], dfn[v]); } } }我复盘这道题时最大的体会是Tarjan不是一个需要死记硬背的算法它本质上就是DFS中“时间戳和回溯值”的配合。你只要在纸上跑一遍三个节点的环再跑一遍一条链瞬间就能理解等号和大于号的区别在哪。Debug的时候把dfn、low、当前检查的边全部打印出来看比盯着代码发呆有效一百倍。3.2 力扣332欧拉路径与字典序最小路线力扣332“重新安排行程”是欧拉路径方向非常经典的一道题。题目给出一堆机票每张机票是[from, to]要求从JFK出发用掉所有机票并且如果有多种合法路线输出字典序最小的那个。这本质上就是求有向图中的欧拉路径而且题目保证输入一定存在合法路径。建图方式上我用map存储每个出发点的所有目的地然后用优先队列存目的地保证每次取出来的是字典序最小的那个。因为Hierholzer算法需要一条一条删除邻接边优先队列的pop天然适合这个操作。跑完DFS后的ans数组需要反转才是从JFK出发的路径。核心代码如下class Solution { public: vectorstring findItinerary(vectorvectorstring tickets) { unordered_mapstring, priority_queuestring, vectorstring, greaterstring g; for (auto t : tickets) g[t[0]].push(t[1]); dfs(JFK, g); reverse(ans.begin(), ans.end()); return ans; } void dfs(string u, unordered_mapstring, priority_queuestring, vectorstring, greaterstring g) { auto it g.find(u); while (it ! g.end() !it-second.empty()) { string v it-second.top(); it-second.pop(); dfs(v, g); } ans.push_back(u); } private: vectorstring ans; };这道题我一开始用vector加sort每次取完一个目的地还要手动删代码很啰嗦而且顺序容易写错。换成优先队列之后清爽多了也更容易检查逻辑。如果你用Python等价做法是对每个邻接表排序然后DFS时pop最后一个元素因为pop最后一个效率更高也能保证字典序最小的节点最后被取出、最后被加到结果里——这里刚好利用了我们前面说的“回溯后插入”的逆序特性。3.3 树的直径题从模板到正权图陷阱树的直径属于“图论专题5”里比较温和的题至少代码短。题目一般长这样给一棵树求两点之间最大距离。解法就是前面说的双BFS第一次BFS找到任意最远点A第二次BFS从A出发找最远点BAB距离就是直径。要是用树形DP也能做但双BFS更直观代码也更短。推荐新手先用双BFS练手。复盘时我做了一个错误示范把双BFS直接套在一张带环的带权图上结果答案偏小。原因前面提过双BFS的贪心成立依赖树的无环结构。在带环正权图里第一次BFS可能找到的不是直径端点局部最远点选错全局就跟着错。要做一般带权图的直径老实跑每个点的Dijkstra然后取最大距离或者用Floyd处理很小的图。这个对比是很多人不知道但又非常关键的知识点面试官很喜欢在这里挖坑。另外还要注意题目给的图如果是稀疏树或者边权全是1才能放心用双BFS。如果题目明确说是一张“图”而不是“树”条件就要打问号。4. 常见问题与调试技巧实录4.1 五个高频卡点速查表我自己刷题和看群里提问总结了专题5最常见的五个卡点列成一张表方便对照。症状根本原因解决办法DFS递归到一半栈溢出图规模大递归深度过深考虑迭代式DFS或调大递归栈限制邻接表不要用vectorvector 导致频繁扩容Tarjan结果少了一整个分量混淆了dfn和low的含义更新时用了low[v]而不是dfn[v]区分dfn是访问顺序low是可达最早时间戳回边更新必须用dfn[v]而不是low[v]欧拉路径代码死循环递归进入邻接节点之前没有删边每次取邻接节点后立即pop/erase再进入递归双BFS在一般图结果错误错误地把树直径的双BFS套到带环图上先判断是否树不是树就改用最短路算法求最大距离孤立点或自环导致答案差1统计度时漏算了自环或BFS初始化漏掉孤立点建图前先明确孤立点是否要计入统计度时把自环按两条度计算4.2 模板如何变成自己的武器我知道很多人的习惯是直接把题解的模板存进笔记然后开始刷下一题。这样效率其实很低。模板只是别人的骨架你要做的是把模板亲手在编辑器里敲一遍然后在本地用几个最简单的图测试比如三节点环、四节点链、带重边的图一步步跟踪变量的变化。我自己的习惯是给模板加注释不是那种“这行是干啥”的废话注释而是“为什么这里用dfn[v]而不是low[v]”这类原理注释。下次遇到变形题翻笔记时回忆起来的速度会快很多。还可以准备一个“模板库”目录把强连通分量、桥、欧拉路径、树的直径的最简模板各存一份配上一道经典题和它的题意用的时候直接搜关键词就能找到。对于训练营节奏建议大家在一个专题里集中刷五到七道同类题不要今天一道强连通、明天一道欧拉路径。图论的算法之间不是彼此孤立的但切换脑子是有成本的。集中刷题能让你把同一个算法吃透到后面见到题就能条件反射地想到对应解法。4.3 性能和复杂度的实测经验专题5涉及的算法复杂度都要心里有数。Tarjan是O(VE)欧拉路径的Hierholzer也是O(VE)双BFS同样O(VE)。Floyd是O(V^3)超过500个节点就要谨慎。比赛和笔试里如果题目数据范围给到10^5级别基本可以排除Floyd和邻接矩阵必须用邻接表加线性或O(E log V)级别的算法。还有一点容易被忽视图论题里邻接表的选择。vectorvector 用起来方便但如果图很大频繁动态扩容会拖慢速度。更稳妥的做法是一次性用vector g[MAXN]这种静态数组或者在输入阶段就根据顶点数和边数预留空间。刷题平台一般不会故意卡这点但实测过50万条边时vector用不好的话耗时差距确实明显。Debug图论题我最推荐的输出方式就是打印检查点比如Tarjan递归前打印“进入udfn1, low1”递归返回后打印“u的low更新为1”这样能看到整个回溯过程。比断点调试适合图论算法的调试模式因为你关心的是整体状态流转不是单行变量的值。最后补一句我的实际体会专题5是我在训练营里第一次感到“图论模板有点不够用了”的地方因为前四天你套模板真的能解决大部分问题但从这天开始单纯背代码已经不行必须理解图结构本身。我个人觉得最有效的做法是所有算法都先在纸上画三张图——一张链、一张环、一张带重边的图然后手动模拟一遍整个算法过程。这个过程花不了半小时但带来的理解远超刷十道题。慢慢来比较快。