最早刷连通图专项时我是真被这套题吓过。暴力解法很简单可一旦数据到了十万级怎么写都绕不过一道坎你得先搞懂强连通分量、割点、桥、边双和点双之间到底什么关系然后才能往缩点之后怎么处理小图这个方向走。后来刷完整整一个专题再看发现框架其实很清晰核心就一套基于DFS时间戳的算法剩下的全是套路变形。这篇先把这个专题的脉络一次讲清楚把SCC、割点、桥三块模板和易错点梳理到位再用几道最有代表性的题目拆开讲思路。适合刚学完基础图论、准备系统刷连通图的选手也适合那种模板抄会了、但一换题就不会缩点的朋友。1. 连通图专题的任务拆解你到底要练哪几种能力很多人打开专题九感觉题量巨大第一反应是找大神的完整代码照抄。这样刷完等于没刷因为连通图这块的题目虽然多但背后的能力项非常集中核心就是五件事。题型图的方向核心算法最常见询问强连通分量SCC有向图Tarjan / Kosaraju缩点后统计入度出度、找可达关系割点与桥无向图Tarjan 的 low/dfn删掉哪些点或边会改变连通性边双连通e-DCC无向图桥 缩点最少加几条边让它变成边双连通点双连通v-DCC无向图边栈 割点块内有几个点在一个环上、奇环问题2-SAT命题图SCC 判定 拓扑选值是否存在满足全部限制的布尔赋值这个表格基本就是整个专题的骨架。你会发现有向图和无向图用的是几乎同一套dfs框架区别只在low[u]的更新来源以及最后判断条件写成大于还是大于等于。为什么这个专题值得单独花时间啃第一缩点是高频套路。几乎所有题目最后一步都是把原图压成一张小图然后在DAG或树上做入度出度统计、最长路、树形DP、LCA这一步能力在后续图论专题里完全通用。第二这些模型在省赛和网络赛里极常见。像最少加几条边变成强连通这种问题原题稍微换个壳就是一道铜牌题动态加边后询问桥的数量更是能在数据结构题里反复出现。第三它能帮你彻底理解DFS时间戳。dfn是发现时间low是回溯时能回到的最小发现时间这个理解透了后面学tarjan求LCA、圆方树都会轻松很多。2. 前置准备Tarjan三件套模板与易错点梳理写题解之前必须先把三套基础模板摆正。我见过太多人SCC会写转到割点桥就崩原因就是对low的语义理解得不够深。这里把三个模板一次讲透。2.1 有向图强连通分量SCC的Tarjan模板SCC的定义不用多解释有向图中任意两点互相可达的最大点集。Tarjan做SCC时每个点入栈当low[u] dfn[u]时说明u是某个SCC的根把栈顶一路弹到u为止这一段就是一个SCC。const int N 10005; int dfn[N], low[N], bel[N], stk[N], inStk[N]; int sccCnt, tim, top; vectorint g[N]; void tarjan(int u) { dfn[u] low[u] tim; stk[top] u; inStk[u] 1; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (inStk[v]) { low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { sccCnt; int v; do { v stk[top--]; inStk[v] 0; bel[v] sccCnt; } while (v ! u); } }有个细节容易被忽略更新已访问节点low时用的是inStk[v]判断而不是dfn[v]。因为横叉边可能指向一个已经出栈、不属于当前DFS栈的节点它的dfn虽然存在但那个节点所在的SCC已经划分完了这时候拿它的dfn去更新当前low会把你当前节点错误拉进那个已经封闭的连通块里。2.2 割点与桥同一个dfs框架下的判据差异无向图的Tarjan不需要栈直接定义比SCC更简单但判据要注意割点low[v] dfn[u]且当u是根节点时还要满足儿子数量 1。桥low[v] dfn[u]严格大于才说明v无法通过其他路径绕回u的祖先。void dfs(int u, int fa) { int child 0; dfn[u] low[u] tim; for (int v : g[u]) { if (!dfn[v]) { child; dfs(v, u); low[u] min(low[u], low[v]); if (low[v] dfn[u] u ! root) isCut[u] 1; if (low[v] dfn[u]) isBridge[u] 1; // 边 u-v 是桥 } else if (v ! fa) { low[u] min(low[u], dfn[v]); } } if (u root child 1) isCut[u] 1; }注意这里我用了v ! fa来判断返祖边前提是题目保证没有重边。一旦题目出现了重边v ! fa就失效了u和v之间有两条边时第二条边会被当成返祖边导致low[v]被更新桥被漏判。处理办法后面在Road Construction那道题里细说这里先记住这个坑。2.3 从下标0开始的链式前向星与反向边SCC的vector写法在竞赛里够用但无向图双向存边时桥判断经常要精确到哪条边而不是哪个邻点所以我习惯用链式前向星并且从下标0开始存边这样反向边就是 e[i^1]。struct Edge { int to, nxt, id; } e[200005]; int head[N], ecnt; void addEdge(int u, int v, int id) { e[ecnt] {v, head[u], id}; head[u] ecnt; }加上边id之后dfs时判断if (e[i].id (lastId ^ 1))还是if (e[i].id lastId)就非常直观。很多模板喜欢用位运算^1跳过反向边因为它要求你从0开始成对加边否则会出错。这也是为什么专题里某些题大家都能过但你抄个从1开始的模板就WA到怀疑人生。3. 第一类必做题缩点后统计入度出度网络学校问题先看一个经典题给定一个有向图表示学校之间软件的传递关系。问两个问题第一问至少要给几个学校发软件才能让所有学校都收到第二问至少要加几条传递边才能让从任意一个学校出发都能到达所有学校。这类题是连通图专题的开胃菜核心思路完全一样对原图求SCC并缩点得到一张DAG。第一问的答案等于DAG中入度为0的节点数因为入度为0的点没有任何上游能给它发软件必须亲自发。第二问的答案等于max(入度为0的数量, 出度为0的数量)但要注意特判如果原图本身已经是强连通图答案是0而不是按公式输出1。为什么第二问是这个公式因为要把DAG变成强连通图最朴素的想法是让每个入度为0的节点和每个出度为0的节点之间连边把头和尾配对。你可以画一条链a→b→c→d入度0的点是a出度0的点是d连一条d→a就整体强连通了。所以答案是头和尾数量的最大值。当只有一个SCC时头和尾其实都是它自己但不需要任何边。缩点之后统计入出度很简单核心代码大概长这样for (int u 1; u n; u) { for (int v : g[u]) { if (bel[u] ! bel[v]) { in[bel[v]]; out[bel[u]]; } } } int a 0, b 0; for (int i 1; i sccCnt; i) { if (in[i] 0) a; if (out[i] 0) b; } if (sccCnt 1) printf(1\n0\n); else printf(%d\n%d\n, a, max(a, b));同系列的奶牛受欢迎的题也是这个套路反向思考缩点后出度为0的分量有多少个。如果恰好只有一个出度为0的分量答案就是这个分量的大小否则答案是0。做这种题时我强烈建议先把缩点后的图和原图关系画出来因为很多WA就出在缩点后忘了把边去重导致入度出度统计重复加。4. 第二类必做题边双连通缩点后连边道路建设类问题这类题的典型描述是给定无向连通图至少添加多少条边才能让任意两点之间都存在两条边不重复的路径。所谓两条边不重复的路径就是这个图变成边双连通也就是说删掉任意一条边图仍然连通。做法分三步先用Tarjan求出所有桥。删掉桥之后剩下的连通块就是边双连通分量。每个边双内部任意两点都有两条路径。把每个边双缩成一个点桥变成树边原图变成一棵树。这时每个缩点度数为1的节点就是叶子答案等于(叶子数 1) / 2。为什么是(叶子数1)/2因为在一棵树上叶子是整棵树最脆弱的位置删掉唯一那条边叶子就孤立了。为了让树变成边双连通必须给叶子两两配对连边一对边可以让两个叶子脱离叶子状态。最少要ceil(叶子数/2)条边对应整数写法就是(leaf 1) / 2。这个题的坑在重边。有些版本题目明确说了可能存在重边此时第2步里的dfs判断不能写成if (v fa) continue;否则重边会被当成返祖边处理桥的统计直接出错。正确的写法是按边编号判断只跳过反向边这一条物理边void tarjan(int u, int lastEid) { dfn[u] low[u] tim; for (int i head[u]; i ! -1; i e[i].nxt) { int v e[i].to; if (i (lastEid ^ 1)) continue; if (!dfn[v]) { tarjan(v, i); low[u] min(low[u], low[v]); if (low[v] dfn[u]) isBridge[i] isBridge[i ^ 1] 1; } else { low[u] min(low[u], dfn[v]); } } }缩点之后统计度数的代码for (int u 1; u n; u) { for (int i head[u]; i ! -1; i e[i].nxt) { if (isBridge[i]) { int a bel[u], b bel[e[i].to]; deg[a]; } } } int leaf 0; for (int i 1; i dcc; i) { if (deg[i] 1) leaf; } int ans (leaf 1) / 2; if (dcc 1) ans 0;这里又有一个特判如果整个图已经边双连通缩点后只有1个点叶子数是0答案不能是0是的公式算出来会是0但有些题在dcc1时需要你输出0所以最好显式特判一下避免边界问题。这类题的进阶版也很多比如温暖过桥那道题的思路先求桥缩点成树然后问加一条边最多能去掉多少桥。答案就是桥的总数减去树的直径因为加在直径两端连成的环覆盖的桥边最多。会了基础缩点这种题就是加一个树的直径DP。5. 第三类进阶题动态加边后的桥维护网络维护问题如果说前面两类题是模板题那动态加边问桥的数量就是连通的综合应用题。题意大概是给一个无向连通图初始有m条边然后有q次操作每次在u和v之间加一条新边问每次加边之后图中还有多少条桥。我第一次做这个题也想过用LCT或者树剖动态维护其实不用因为加边只会让桥减少永远不会增加而且每次加边把u到v路径上所有桥变成非桥后这些边就再也不会变回桥。所以思路是这样先Tarjan求出所有桥把桥的数量记为ans。把桥断掉后原图被分成若干边双连通分量。将这些分量缩点桥变成树边原图变成一棵树此时树上每条边都对应原图一条桥。每次加边 (u,v)等价于在树上把u到v路径上的所有边都覆盖一次。被覆盖的边不再是桥所以每覆盖一条树边ans就减1。每条边最多被覆盖一次。因此用并查集做路径压缩从深度深的点向上跳跳到父子边已经被覆盖过的地方就跳到更高的祖先这样每条边只会操作一次。关键代码逻辑int find(int x) { return pre[x] x ? x : pre[x] find(pre[x]); } void cover(int u, int stop, int ans) { while (depth[u] depth[stop]) { u find(u); // 找到从u向上第一个还没被覆盖的节点 if (depth[u] depth[stop]) break; ans--; // 覆盖了 u 到 parent[u] 这条树边 pre[u] find(parent[u]); // 把u并入父节点下次直接跳过 u pre[u]; } } void link(int u, int v, int ans) { int l lca(u, v); cover(u, l, ans); cover(v, l, ans); printf(%d\n, ans); }这里pre[u]初始都指向自己表示这条边还没被覆盖。每次覆盖一条边就把u的pre指向它父亲链上第一个未覆盖的节点实现跳跃式压缩。因为每条边只会被覆盖一次所有操作的总复杂度是O((nq) log n)级别瓶颈反而是求LCA。我一开始写这题时用树链剖分维护桥的个数代码比并查集写法长了三倍后来发现这个题每次只问桥的总数不需要区间查询完全可以用离线均摊并查集跳祖先来解决。这也算是一个经验动态图题优先想单调性桥的数量只会减少这个性质直接决定了能不能用并查集。6. 缩点之外的扩展方向点双、奇环与2-SAT做完强连通和边双专题还剩两座大山点双连通分量和2-SAT。它们和前面有一点联系但模型完全不同。6.1 2-SAT把布尔命题变成强连通判定2-SAT的经典形式是有n个布尔变量给定若干或形式限制问是否存在一组赋值满足全部限制。做法是每个变量拆成两个节点x表示选真?x表示选假。根据逻辑蕴含关系建图然后求SCC。判无解的标准很简单如果某个变量x和?x在同一个SCC里说明选真必须选真这种循环矛盾出现无解。如果需要输出方案有个很常用的技巧Tarjan跑完的bel编号是逆拓扑序即bel值小的SCC在拓扑序中位置靠后。判断时直接取bel值较小的那个点作为选择结果。例如for (int i 1; i n; i) { if (bel[i * 2] bel[i * 2 1]) printf(NO\n); } // 输出方案时 // 若 bel[i*2] bel[i*21] 则变量取 false为什么Tarjan算法在缩点时会按DFS完成顺序给SCC编号完成时间晚即先弹栈的SCC编号反而小。这里涉及一个拓扑序的性质建议自己画两个互相指向的连通块验证一遍比死记硬背可靠。6.2 点双连通与奇环圆桌骑士类问题点双连通分量是有向无向图里最复杂的一块它和边双最大的区别是一个割点可以属于多个点双连通分量所以Tarjan求点双时要用边栈弹到当前边为止。经典问题给一个无向图求不在任何奇环中的点数。这个问题的核心结论是点双连通分量内如果存在一个奇环那么这个分量内的所有点都在某个奇环上。原因可以用通过两条不同路径把奇环外点接进奇环来理解点双保证了任意两个点之间有两条无公共边的路径。所以流程是用Tarjan找出所有点双对每个点双做二分图染色。如果一个点双不是二分图说明包含奇环那这个点双里所有点都标记为可以在奇环上最后统计没被标记的点。点双模板里最容易错的地方找点双时遇到割点割点会被放进多个分量所以染色时不能简单用全局vis数组要先标记这个点双内的所有点只对这些点进行染色。另外每个点双的染色起点要放在一个内部节点上而不是随便从1开始全局跑否则环被割点切开后染色信息会串。7. 刷题阶段我踩过的坑与排查顺序这一节只讲我实际在专题里反复踩的坑按出现频率排序。第一坑重边判断。桥的题目里十有八九有重边。判断桥时如果写的是if (v fa) continue;遇到两条平行边就会漏判。统一改用边编号if (i (last ^ 1)) continue;之后这类问题彻底消失。这算是我刷专题九最大的收获之一。第二坑递归爆栈。Tarjan是递归DFS当图是一条长链时深度可能到n。老OJ的栈空间比较保守链式图会直接栈溢出。Windows下可以加编译器指令开大栈#pragma comment(linker, /STACK:1024000000,1024000000)如果是Linux环境可以尝试用ulimit -s unlimited或者干脆改成非递归实现。强烈建议日常就用非递归模板练熟因为有些题目卡栈程度很变态。第三坑输出格式与初始化。多组数据的题经常坑在这两件事。每个用例前都要重新初始化dfn、low、head这些数组尤其是tim和sccCnt必须清零。我见过有人把tim忘了清导致dfn不断变大最后无向图的low更新全部错乱。另外输出格式要注意是Case #x: y还是输出一个整数即可专题里两种都有。第四坑特判太多但漏了。缩点后只有1个节点的题比如图已经强连通/边双连通答案往往是0而不是套公式产生的结果。或者图本身不连通的时候第一问和第二问的答案口径也会变化。我的建议是拿到题先想清楚这四种边界n1、图本身强连通、缩点后只剩1个节点、原图根本不联通。第五坑遍历缩点后度数时忽略重边。有些题的缩点边统计需要去重否则入度会被重复累加。虽然大多数题目连续加两次相同方向的对答案没影响但有题目会统计入度为0的点数重复加会把入度累出1导致漏算。稳妥做法是用set或排序去重虽然慢一点但省得WA到怀疑人生。第六坑用Kosaraju一把梭到底。如果只是判断强连通个数Kosaraju写起来更短但问题是它要做两次DFS缩点顺序和原图的可达性关系更难直接用于2-SAT输出。我后来统一改成Tarjan一个模板通吃所有情况避免切换思维。刷这个专题的速度不要贪快。基础模板半天就能抄会但缩点之后的建模能力只能靠一道题一道题积累。我的建议顺序是先做两到三道SCC入出度统计题再做两道桥和边双然后上动态加边题最后才是点双和2-SAT。每做完一类题把自己的模板修补一遍修到能够直接默写出来为止。最后分享一个小体会连通图专题最值钱的地方不在会求SCC而在于你看到图中可达/必经/删边删点/最少加边这些字眼时能第一时间想到缩点之后怎么处理小图。这个反应速度练好了这个专题就算真正吃透了。