最早刷連通圖專項時我是真被這套題嚇過。暴力解法很簡單可一旦數(shù)據(jù)到了十萬級怎么寫都繞不過一道坎你得先搞懂強連通分量、割點、橋、邊雙和點雙之間到底什么關系然后才能往縮點之后怎么處理小圖這個方向走。后來刷完整整一個專題再看發(fā)現(xiàn)框架其實很清晰核心就一套基于DFS時間戳的算法剩下的全是套路變形。這篇先把這個專題的脈絡一次講清楚把SCC、割點、橋三塊模板和易錯點梳理到位再用幾道最有代表性的題目拆開講思路。適合剛學完基礎圖論、準備系統(tǒng)刷連通圖的選手也適合那種模板抄會了、但一換題就不會縮點的朋友。1. 連通圖專題的任務拆解你到底要練哪幾種能力很多人打開專題九感覺題量巨大第一反應是找大神的完整代碼照抄。這樣刷完等于沒刷因為連通圖這塊的題目雖然多但背后的能力項非常集中核心就是五件事。題型圖的方向核心算法最常見詢問強連通分量SCC有向圖Tarjan / Kosaraju縮點后統(tǒng)計入度出度、找可達關系割點與橋無向圖Tarjan 的 low/dfn刪掉哪些點或邊會改變連通性邊雙連通e-DCC無向圖橋 縮點最少加幾條邊讓它變成邊雙連通點雙連通v-DCC無向圖邊棧 割點塊內有幾個點在一個環(huán)上、奇環(huán)問題2-SAT命題圖SCC 判定 拓撲選值是否存在滿足全部限制的布爾賦值這個表格基本就是整個專題的骨架。你會發(fā)現(xiàn)有向圖和無向圖用的是幾乎同一套dfs框架區(qū)別只在low[u]的更新來源以及最后判斷條件寫成大于還是大于等于。為什么這個專題值得單獨花時間啃第一縮點是高頻套路。幾乎所有題目最后一步都是把原圖壓成一張小圖然后在DAG或樹上做入度出度統(tǒng)計、最長路、樹形DP、LCA這一步能力在后續(xù)圖論專題里完全通用。第二這些模型在省賽和網絡賽里極常見。像最少加幾條邊變成強連通這種問題原題稍微換個殼就是一道銅牌題動態(tài)加邊后詢問橋的數(shù)量更是能在數(shù)據(jù)結構題里反復出現(xiàn)。第三它能幫你徹底理解DFS時間戳。dfn是發(fā)現(xiàn)時間low是回溯時能回到的最小發(fā)現(xiàn)時間這個理解透了后面學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); } }有個細節(jié)容易被忽略更新已訪問節(jié)點low時用的是inStk[v]判斷而不是dfn[v]。因為橫叉邊可能指向一個已經出棧、不屬于當前DFS棧的節(jié)點它的dfn雖然存在但那個節(jié)點所在的SCC已經劃分完了這時候拿它的dfn去更新當前l(fā)ow會把你當前節(jié)點錯誤拉進那個已經封閉的連通塊里。2.2 割點與橋同一個dfs框架下的判據(jù)差異無向圖的Tarjan不需要棧直接定義比SCC更簡單但判據(jù)要注意割點low[v] dfn[u]且當u是根節(jié)點時還要滿足兒子數(shù)量 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來判斷返祖邊前提是題目保證沒有重邊。一旦題目出現(xiàn)了重邊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. 第一類必做題縮點后統(tǒng)計入度出度網絡學校問題先看一個經典題給定一個有向圖表示學校之間軟件的傳遞關系。問兩個問題第一問至少要給幾個學校發(fā)軟件才能讓所有學校都收到第二問至少要加幾條傳遞邊才能讓從任意一個學校出發(fā)都能到達所有學校。這類題是連通圖專題的開胃菜核心思路完全一樣對原圖求SCC并縮點得到一張DAG。第一問的答案等于DAG中入度為0的節(jié)點數(shù)因為入度為0的點沒有任何上游能給它發(fā)軟件必須親自發(fā)。第二問的答案等于max(入度為0的數(shù)量, 出度為0的數(shù)量)但要注意特判如果原圖本身已經是強連通圖答案是0而不是按公式輸出1。為什么第二問是這個公式因為要把DAG變成強連通圖最樸素的想法是讓每個入度為0的節(jié)點和每個出度為0的節(jié)點之間連邊把頭和尾配對。你可以畫一條鏈a→b→c→d入度0的點是a出度0的點是d連一條d→a就整體強連通了。所以答案是頭和尾數(shù)量的最大值。當只有一個SCC時頭和尾其實都是它自己但不需要任何邊?？s點之后統(tǒng)計入出度很簡單核心代碼大概長這樣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就出在縮點后忘了把邊去重導致入度出度統(tǒng)計重復加。4. 第二類必做題邊雙連通縮點后連邊道路建設類問題這類題的典型描述是給定無向連通圖至少添加多少條邊才能讓任意兩點之間都存在兩條邊不重復的路徑。所謂兩條邊不重復的路徑就是這個圖變成邊雙連通也就是說刪掉任意一條邊圖仍然連通。做法分三步先用Tarjan求出所有橋。刪掉橋之后剩下的連通塊就是邊雙連通分量。每個邊雙內部任意兩點都有兩條路徑。把每個邊雙縮成一個點橋變成樹邊原圖變成一棵樹。這時每個縮點度數(shù)為1的節(jié)點就是葉子答案等于(葉子數(shù) 1) / 2。為什么是(葉子數(shù)1)/2因為在一棵樹上葉子是整棵樹最脆弱的位置刪掉唯一那條邊葉子就孤立了。為了讓樹變成邊雙連通必須給葉子兩兩配對連邊一對邊可以讓兩個葉子脫離葉子狀態(tài)。最少要ceil(葉子數(shù)/2)條邊對應整數(shù)寫法就是(leaf 1) / 2。這個題的坑在重邊。有些版本題目明確說了可能存在重邊此時第2步里的dfs判斷不能寫成if (v fa) continue;否則重邊會被當成返祖邊處理橋的統(tǒng)計直接出錯。正確的寫法是按邊編號判斷只跳過反向邊這一條物理邊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]); } } }縮點之后統(tǒng)計度數(shù)的代碼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個點葉子數(shù)是0答案不能是0是的公式算出來會是0但有些題在dcc1時需要你輸出0所以最好顯式特判一下避免邊界問題。這類題的進階版也很多比如溫暖過橋那道題的思路先求橋縮點成樹然后問加一條邊最多能去掉多少橋。答案就是橋的總數(shù)減去樹的直徑因為加在直徑兩端連成的環(huán)覆蓋的橋邊最多。會了基礎縮點這種題就是加一個樹的直徑DP。5. 第三類進階題動態(tài)加邊后的橋維護網絡維護問題如果說前面兩類題是模板題那動態(tài)加邊問橋的數(shù)量就是連通的綜合應用題。題意大概是給一個無向連通圖初始有m條邊然后有q次操作每次在u和v之間加一條新邊問每次加邊之后圖中還有多少條橋。我第一次做這個題也想過用LCT或者樹剖動態(tài)維護其實不用因為加邊只會讓橋減少永遠不會增加而且每次加邊把u到v路徑上所有橋變成非橋后這些邊就再也不會變回橋。所以思路是這樣先Tarjan求出所有橋把橋的數(shù)量記為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向上第一個還沒被覆蓋的節(jié)點 if (depth[u] depth[stop]) break; ans--; // 覆蓋了 u 到 parent[u] 這條樹邊 pre[u] find(parent[u]); // 把u并入父節(jié)點下次直接跳過 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指向它父親鏈上第一個未覆蓋的節(jié)點實現(xiàn)跳躍式壓縮。因為每條邊只會被覆蓋一次所有操作的總復雜度是O((nq) log n)級別瓶頸反而是求LCA。我一開始寫這題時用樹鏈剖分維護橋的個數(shù)代碼比并查集寫法長了三倍后來發(fā)現(xiàn)這個題每次只問橋的總數(shù)不需要區(qū)間查詢完全可以用離線均攤并查集跳祖先來解決。這也算是一個經驗動態(tài)圖題優(yōu)先想單調性橋的數(shù)量只會減少這個性質直接決定了能不能用并查集。6. 縮點之外的擴展方向點雙、奇環(huán)與2-SAT做完強連通和邊雙專題還剩兩座大山點雙連通分量和2-SAT。它們和前面有一點聯(lián)系但模型完全不同。6.1 2-SAT把布爾命題變成強連通判定2-SAT的經典形式是有n個布爾變量給定若干或形式限制問是否存在一組賦值滿足全部限制。做法是每個變量拆成兩個節(jié)點x表示選真?x表示選假。根據(jù)邏輯蘊含關系建圖然后求SCC。判無解的標準很簡單如果某個變量x和?x在同一個SCC里說明選真必須選真這種循環(huán)矛盾出現(xiàn)無解。如果需要輸出方案有個很常用的技巧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 點雙連通與奇環(huán)圓桌騎士類問題點雙連通分量是有向無向圖里最復雜的一塊它和邊雙最大的區(qū)別是一個割點可以屬于多個點雙連通分量所以Tarjan求點雙時要用邊棧彈到當前邊為止。經典問題給一個無向圖求不在任何奇環(huán)中的點數(shù)。這個問題的核心結論是點雙連通分量內如果存在一個奇環(huán)那么這個分量內的所有點都在某個奇環(huán)上。原因可以用通過兩條不同路徑把奇環(huán)外點接進奇環(huán)來理解點雙保證了任意兩個點之間有兩條無公共邊的路徑。所以流程是用Tarjan找出所有點雙對每個點雙做二分圖染色。如果一個點雙不是二分圖說明包含奇環(huán)那這個點雙里所有點都標記為可以在奇環(huán)上最后統(tǒng)計沒被標記的點。點雙模板里最容易錯的地方找點雙時遇到割點割點會被放進多個分量所以染色時不能簡單用全局vis數(shù)組要先標記這個點雙內的所有點只對這些點進行染色。另外每個點雙的染色起點要放在一個內部節(jié)點上而不是隨便從1開始全局跑否則環(huán)被割點切開后染色信息會串。7. 刷題階段我踩過的坑與排查順序這一節(jié)只講我實際在專題里反復踩的坑按出現(xiàn)頻率排序。第一坑重邊判斷。橋的題目里十有八九有重邊。判斷橋時如果寫的是if (v fa) continue;遇到兩條平行邊就會漏判。統(tǒng)一改用邊編號if (i (last ^ 1)) continue;之后這類問題徹底消失。這算是我刷專題九最大的收獲之一。第二坑遞歸爆棧。Tarjan是遞歸DFS當圖是一條長鏈時深度可能到n。老OJ的?？臻g比較保守鏈式圖會直接棧溢出。Windows下可以加編譯器指令開大棧#pragma comment(linker, /STACK:1024000000,1024000000)如果是Linux環(huán)境可以嘗試用ulimit -s unlimited或者干脆改成非遞歸實現(xiàn)。強烈建議日常就用非遞歸模板練熟因為有些題目卡棧程度很變態(tài)。第三坑輸出格式與初始化。多組數(shù)據(jù)的題經?？釉谶@兩件事。每個用例前都要重新初始化dfn、low、head這些數(shù)組尤其是tim和sccCnt必須清零。我見過有人把tim忘了清導致dfn不斷變大最后無向圖的low更新全部錯亂。另外輸出格式要注意是Case #x: y還是輸出一個整數(shù)即可專題里兩種都有。第四坑特判太多但漏了?？s點后只有1個節(jié)點的題比如圖已經強連通/邊雙連通答案往往是0而不是套公式產生的結果?；蛘邎D本身不連通的時候第一問和第二問的答案口徑也會變化。我的建議是拿到題先想清楚這四種邊界n1、圖本身強連通、縮點后只剩1個節(jié)點、原圖根本不聯(lián)通。第五坑遍歷縮點后度數(shù)時忽略重邊。有些題的縮點邊統(tǒng)計需要去重否則入度會被重復累加。雖然大多數(shù)題目連續(xù)加兩次相同方向的對答案沒影響但有題目會統(tǒng)計入度為0的點數(shù)重復加會把入度累出1導致漏算。穩(wěn)妥做法是用set或排序去重雖然慢一點但省得WA到懷疑人生。第六坑用Kosaraju一把梭到底。如果只是判斷強連通個數(shù)Kosaraju寫起來更短但問題是它要做兩次DFS縮點順序和原圖的可達性關系更難直接用于2-SAT輸出。我后來統(tǒng)一改成Tarjan一個模板通吃所有情況避免切換思維。刷這個專題的速度不要貪快。基礎模板半天就能抄會但縮點之后的建模能力只能靠一道題一道題積累。我的建議順序是先做兩到三道SCC入出度統(tǒng)計題再做兩道橋和邊雙然后上動態(tài)加邊題最后才是點雙和2-SAT。每做完一類題把自己的模板修補一遍修到能夠直接默寫出來為止。最后分享一個小體會連通圖專題最值錢的地方不在會求SCC而在于你看到圖中可達/必經/刪邊刪點/最少加邊這些字眼時能第一時間想到縮點之后怎么處理小圖。這個反應速度練好了這個專題就算真正吃透了。