1. 項(xiàng)目概述為什么你需要一個(gè)“自用”的并查集模板在算法競(jìng)賽和日常開發(fā)中并查集Union-Find是一個(gè)出場(chǎng)率極高的數(shù)據(jù)結(jié)構(gòu)。它專門用來處理一些不交集的合并與查詢問題比如判斷社交網(wǎng)絡(luò)中的兩個(gè)人是否屬于同一個(gè)朋友圈或者管理圖中連通分量的動(dòng)態(tài)合并。我第一次接觸并查集是在解決一個(gè)“親戚關(guān)系”問題時(shí)當(dāng)時(shí)覺得這個(gè)結(jié)構(gòu)簡(jiǎn)直是為這類問題量身定做的。但很快我就發(fā)現(xiàn)雖然并查集原理簡(jiǎn)單但在實(shí)際編碼中如果不精心設(shè)計(jì)很容易寫出效率低下或者邊界情況處理不當(dāng)?shù)拇a。這就是“自用模板”的價(jià)值所在。它不是一個(gè)從教科書上抄下來的通用代碼片段而是經(jīng)過無數(shù)次調(diào)試、優(yōu)化和實(shí)戰(zhàn)檢驗(yàn)后沉淀下來的、最適合我個(gè)人或者說適合大多數(shù)追求效率和穩(wěn)健性的開發(fā)者的代碼結(jié)晶。一個(gè)好的自用模板意味著你在遇到相關(guān)問題時(shí)可以像調(diào)用標(biāo)準(zhǔn)庫函數(shù)一樣自信地粘貼、微調(diào)而無需擔(dān)心隱藏的bug或性能陷阱。它封裝了路徑壓縮、按秩合并等核心優(yōu)化處理了初始化、查找、合并等所有基本操作甚至預(yù)埋了一些高級(jí)功能的接口。今天我就來詳細(xì)拆解我一直在用的這個(gè)并查集模板從設(shè)計(jì)思路到每一行代碼的考量再到實(shí)戰(zhàn)中踩過的坑和總結(jié)的技巧希望能幫你構(gòu)建或優(yōu)化屬于你自己的那一份“利器”。2. 模板核心設(shè)計(jì)與思路拆解2.1 數(shù)據(jù)結(jié)構(gòu)選型數(shù)組是唯一的主角并查集最經(jīng)典、最高效的實(shí)現(xiàn)方式就是使用數(shù)組。我的模板基于一個(gè)一維整型數(shù)組parent[]來構(gòu)建。數(shù)組的下標(biāo)代表一個(gè)元素或節(jié)點(diǎn)的編號(hào)而數(shù)組存儲(chǔ)的值代表這個(gè)元素的“父節(jié)點(diǎn)”編號(hào)。為什么是數(shù)組而不是其他結(jié)構(gòu)訪問速度極快通過下標(biāo)進(jìn)行隨機(jī)訪問是O(1)時(shí)間復(fù)雜度這對(duì)于并查集最核心的find查找根節(jié)點(diǎn)操作至關(guān)重要。內(nèi)存連續(xù)緩存友好現(xiàn)代CPU的緩存機(jī)制對(duì)連續(xù)內(nèi)存訪問非常高效能進(jìn)一步提升批量操作的速度。實(shí)現(xiàn)簡(jiǎn)單直觀用數(shù)組模擬樹形結(jié)構(gòu)概念清晰代碼簡(jiǎn)潔不易出錯(cuò)。在模板中我通常這樣初始化vectorint parent; vectorint rank; // 用于按秩合并有時(shí)也用size表示集合大小使用vector而不是原生數(shù)組是為了獲得動(dòng)態(tài)大小和更安全的內(nèi)存管理這在問題規(guī)模不確定時(shí)非常方便。2.2 兩大優(yōu)化基石路徑壓縮與按秩合并一個(gè)樸素的并查集在最壞情況下比如退化成一條鏈每次查找的時(shí)間復(fù)雜度會(huì)退化到O(n)。因此優(yōu)化是必須的。我的模板同時(shí)集成了兩大“神級(jí)”優(yōu)化確保均攤時(shí)間復(fù)雜度接近常數(shù)級(jí)。2.2.1 路徑壓縮讓樹變得更扁在find(x)函數(shù)中我們?cè)趯ふ腋?jié)點(diǎn)的同時(shí)將路徑上所有節(jié)點(diǎn)的父節(jié)點(diǎn)直接指向根節(jié)點(diǎn)。這樣下次查詢這些節(jié)點(diǎn)時(shí)就能一步到位。int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 遞歸進(jìn)行路徑壓縮 } return parent[x]; }為什么用遞歸遞歸寫法非常簡(jiǎn)潔清晰地表達(dá)了“找到根并把我及我的祖先們都掛到根上”這個(gè)意圖。雖然存在遞歸棧開銷但在路徑壓縮的作用下樹的高度極低遞歸深度很小這點(diǎn)開銷完全可以接受。當(dāng)然迭代寫法也可以但代碼稍顯冗長(zhǎng)。2.2.2 按秩合并避免樹的不平衡生長(zhǎng)當(dāng)合并兩個(gè)集合時(shí)我們總是將“秩”較小樹更矮或元素更少的樹合并到“秩”較大的樹下。這能有效避免合并后樹的高度急劇增加。 在我的模板中“秩”通常指樹的高度rank。void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 已在同一集合 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { // 高度相同時(shí)任意合并但被合并的樹高度會(huì)增加1 parent[rootY] rootX; rank[rootX]; } }為什么選擇高度作為“秩”相比于集合大小樹的高度更直接地影響find操作的效率?？刂聘叨染褪强刂谱顗牟樵兟窂降拈L(zhǎng)度。有些實(shí)現(xiàn)會(huì)用集合大小size作為秩這在需要頻繁查詢集合大小的場(chǎng)景下更有優(yōu)勢(shì)但就純粹的合并查詢效率而言高度秩是經(jīng)典選擇。2.3 模板的擴(kuò)展性思考一個(gè)優(yōu)秀的自用模板不能只解決標(biāo)準(zhǔn)問題。我通常會(huì)為它預(yù)留一些擴(kuò)展點(diǎn)集合大小記錄增加一個(gè)size[]數(shù)組在合并時(shí)維護(hù)每個(gè)根節(jié)點(diǎn)所屬集合的元素個(gè)數(shù)。這在解決一些需要知道連通塊大小的問題時(shí)非常有用。動(dòng)態(tài)擴(kuò)容如果問題初始元素?cái)?shù)未知模板應(yīng)支持動(dòng)態(tài)添加新元素即擴(kuò)展parent數(shù)組。持久化/可撤銷高級(jí)需求通過記錄操作日志實(shí)現(xiàn)合并操作的撤銷這在一些離線算法中會(huì)用到。我的基礎(chǔ)模板不包含此部分但結(jié)構(gòu)上會(huì)保持清晰以便日后添加。3. 完整模板代碼與逐行解析下面是我最常用的C并查集模板。它包含了初始化、查找含路徑壓縮、合并按秩合并以及一個(gè)判斷是否連通的輔助函數(shù)。class UnionFind { private: vectorint parent; vectorint rank; // 基于高度的秩 public: // 構(gòu)造函數(shù)初始化n個(gè)元素的并查集每個(gè)元素自成集合 UnionFind(int n) { parent.resize(n); rank.resize(n, 0); // 初始高度為0 for (int i 0; i n; i) { parent[i] i; // 每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)初始化為自己 } } // 查找操作找到元素x所在集合的根節(jié)點(diǎn)并進(jìn)行路徑壓縮 int find(int x) { // 遞歸寫法簡(jiǎn)潔明了。如果x不是根就遞歸找根的根并把x的父節(jié)點(diǎn)設(shè)為根。 if (parent[x] ! x) { parent[x] find(parent[x]); // 核心路徑壓縮在此發(fā)生 } return parent[x]; } // 合并操作將元素x和y所在的集合合并 void unite(int x, int y) { int rootX find(x); int rootY find(y); // 如果已經(jīng)在同一集合直接返回避免冗余操作和秩的錯(cuò)誤增加 if (rootX rootY) { return; } // 按秩合并將矮樹掛到高樹下 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { // 兩棵樹高度相同任意合并但合并后樹的高度會(huì)增加1 parent[rootY] rootX; rank[rootX]; // 只有高度相同時(shí)合并后的樹高度才需要1 } } // 查詢操作判斷元素x和y是否屬于同一集合 bool isConnected(int x, int y) { return find(x) find(y); } // 可選獲取當(dāng)前集合的數(shù)量連通分量數(shù) int countSets() { int cnt 0; for (int i 0; i parent.size(); i) { if (parent[i] i) { // 根節(jié)點(diǎn)的父節(jié)點(diǎn)是自己 cnt; } } return cnt; } };關(guān)鍵行解析與設(shè)計(jì)理由parent.resize(n); rank.resize(n, 0);一次性分配內(nèi)存避免后續(xù)動(dòng)態(tài)調(diào)整的開銷。將rank初始化為0符合“單節(jié)點(diǎn)樹高度為0”的定義。if (parent[x] ! x) { parent[x] find(parent[x]); }這是路徑壓縮的遞歸實(shí)現(xiàn)。它不僅在本次查找中壓縮了從x到根的路徑也遞歸地壓縮了路徑上所有祖先節(jié)點(diǎn)的路徑。這是效率的關(guān)鍵。if (rootX rootY) { return; }這是一個(gè)重要的剪枝。先進(jìn)行查找如果根相同則無需合并。這避免了無意義的父節(jié)點(diǎn)賦值和可能的rank錯(cuò)誤增加。rank[rootX]這行代碼只在兩棵樹高度相等時(shí)執(zhí)行。因?yàn)閷ootY掛到rootX下以rootX為根的樹高度增加了1。如果rootX本來就比rootY高合并不會(huì)增加整體高度所以不需要rank[rootX]。這是按秩合并的精髓務(wù)必理解。isConnected函數(shù)直接比較根節(jié)點(diǎn)。這里隱式地進(jìn)行了路徑壓縮因?yàn)檎{(diào)用了find這是一個(gè)有益副作用。countSets函數(shù)遍歷所有節(jié)點(diǎn)統(tǒng)計(jì)父節(jié)點(diǎn)是自己的節(jié)點(diǎn)數(shù)即根節(jié)點(diǎn)數(shù)。這個(gè)方法的時(shí)間復(fù)雜度是O(n)通常只在最終需要時(shí)調(diào)用一次。4. 實(shí)戰(zhàn)應(yīng)用場(chǎng)景與模板適配技巧并查集模板是死的問題是活的。直接套用模板有時(shí)不夠需要根據(jù)具體場(chǎng)景進(jìn)行微調(diào)。4.1 場(chǎng)景一動(dòng)態(tài)連通性問題LeetCode 典型題問題特征給你一系列節(jié)點(diǎn)對(duì)邊需要你動(dòng)態(tài)地回答“某兩個(gè)節(jié)點(diǎn)是否連通”這類查詢。模板直接應(yīng)用上述標(biāo)準(zhǔn)模板完全適用。初始化時(shí)節(jié)點(diǎn)數(shù)設(shè)為n然后遍歷邊數(shù)組對(duì)每一條邊[u, v]調(diào)用unite(u, v)。查詢時(shí)調(diào)用isConnected(a, b)。注意事項(xiàng)節(jié)點(diǎn)編號(hào)通常從0或1開始。如果從1開始初始化UnionFind時(shí)傳入n1并忽略下標(biāo)0這樣更符合直覺。4.2 場(chǎng)景二需要統(tǒng)計(jì)連通分量大小問題特征在合并過程中可能需要知道某個(gè)節(jié)點(diǎn)所在集合當(dāng)前有多少個(gè)元素例如LeetCode 的“最大島嶼面積”變體。模板適配在類中增加一個(gè)vectorint size。初始化size[i] 1。修改unite函數(shù)合并時(shí)將小集合的根掛到大集合的根下并更新大集合的size。if (size[rootX] size[rootY]) { swap(rootX, rootY); // 確保rootX是更大的集合 } parent[rootY] rootX; size[rootX] size[rootY]; // 更新大小 // 按大小合并時(shí)rank可能不再需要或用于另一種平衡策略技巧此時(shí)“秩”的概念可以從“高度”轉(zhuǎn)變?yōu)椤按笮　卑创笮『喜⒁材苡行Э刂茦涓卟⑶翌~外獲得了集合大小的信息。4.3 場(chǎng)景三帶權(quán)并查集擴(kuò)展關(guān)系問題特征節(jié)點(diǎn)間不僅有連通關(guān)系還有某種權(quán)值關(guān)系如距離、差值、相對(duì)關(guān)系等。典型問題是“判斷算式合法性”或“食物鏈”問題。模板適配這是高級(jí)應(yīng)用需要大幅修改模板。核心是增加一個(gè)vectorint weight數(shù)組weight[x]表示節(jié)點(diǎn)x到其父節(jié)點(diǎn)parent[x]的權(quán)值關(guān)系。find函數(shù)在遞歸查找根節(jié)點(diǎn)時(shí)需要同時(shí)更新權(quán)值。路徑壓縮后weight[x]應(yīng)變?yōu)閤到新根節(jié)點(diǎn)的權(quán)值這需要通過遞歸過程累積計(jì)算。unite函數(shù)合并時(shí)根據(jù)題目給出的x和y之間的權(quán)值關(guān)系以及它們各自到根節(jié)點(diǎn)的權(quán)值推導(dǎo)出兩個(gè)根節(jié)點(diǎn)之間的應(yīng)有權(quán)值然后進(jìn)行合并和權(quán)值設(shè)置。心得帶權(quán)并查集的關(guān)鍵在于向量思維。把權(quán)值看作向量合并時(shí)就是向量的加減運(yùn)算。理解并推導(dǎo)出根節(jié)點(diǎn)間權(quán)值的計(jì)算公式是解決這類問題的核心模板只是實(shí)現(xiàn)這個(gè)計(jì)算的框架。4.4 場(chǎng)景四離線處理與可撤銷合并問題特征操作序列中混合了合并和查詢但可能需要按照特定順序如逆序處理或者需要嘗試性的合并與回退如某些搜索算法。模板適配標(biāo)準(zhǔn)模板不支持撤銷。需要實(shí)現(xiàn)一個(gè)可撤銷并查集。核心改動(dòng)不使用路徑壓縮因?yàn)閴嚎s后父指針改變難以撤銷只使用按秩合并。記錄操作棧在unite時(shí)將合并前的狀態(tài)哪個(gè)根被掛到哪個(gè)根下以及秩的變化壓入棧中。撤銷操作從棧中彈出狀態(tài)恢復(fù)parent和rank數(shù)組。注意事項(xiàng)失去了路徑壓縮單次find操作復(fù)雜度會(huì)退化到O(log n)。因此只在確實(shí)需要撤銷功能的場(chǎng)景下使用此變體。5. 常見“坑點(diǎn)”與調(diào)試技巧實(shí)錄即使有了模板在實(shí)際編碼中依然會(huì)遭遇各種問題。下面是我總結(jié)的幾個(gè)高頻“坑點(diǎn)”和應(yīng)對(duì)策略。5.1 初始化錯(cuò)誤節(jié)點(diǎn)編號(hào)與數(shù)組下標(biāo)問題題目說節(jié)點(diǎn)編號(hào)是1~N你創(chuàng)建了大小為N的UnionFind對(duì)象訪問parent[1]沒問題但當(dāng)你嘗試unite(N, N)時(shí)發(fā)生了數(shù)組越界。原因大小為N的數(shù)組有效下標(biāo)是0~N-1。節(jié)點(diǎn)編號(hào)N對(duì)應(yīng)下標(biāo)N越界了。解決統(tǒng)一使用0-indexed從0開始的內(nèi)部處理。這是最安全、最不容易出錯(cuò)的方式。// 構(gòu)造函數(shù) UnionFind uf(n); // 假設(shè)n是節(jié)點(diǎn)最大編號(hào) // 當(dāng)處理一條連接u-v的邊時(shí)u, v從1開始 uf.unite(u - 1, v - 1); // 外部輸入減1轉(zhuǎn)換為內(nèi)部下標(biāo)或者在類內(nèi)部做轉(zhuǎn)換但外部轉(zhuǎn)換更清晰。我的模板默認(rèn)接受的就是0-indexed的輸入。5.2 路徑壓縮的遞歸深度與棧溢出問題在極端大的數(shù)據(jù)集如10^5級(jí)別上如果初始合并形成了一條長(zhǎng)鏈第一次深度查找時(shí)遞歸版本的find可能導(dǎo)致棧溢出。分析與解決實(shí)際情況在同時(shí)使用按秩合并優(yōu)化后樹的高度會(huì)被有效控制在O(log n)級(jí)別遞歸深度很少會(huì)達(dá)到導(dǎo)致棧溢出的程度通常遞歸深度超過幾千才需擔(dān)心。保險(xiǎn)起見可以使用迭代寫法實(shí)現(xiàn)路徑壓縮。int find(int x) { int root x; while (parent[root] ! root) { root parent[root]; // 先找到根 } // 二次迭代進(jìn)行路徑壓縮 while (parent[x] ! root) { int next parent[x]; parent[x] root; x next; } return root; }迭代寫法稍長(zhǎng)但絕對(duì)安全。我的經(jīng)驗(yàn)是在算法競(jìng)賽和絕大多數(shù)工程場(chǎng)景中遞歸版本完全夠用且更優(yōu)雅。5.3 按秩合并中“秩”的誤更新問題在unite函數(shù)中錯(cuò)誤地在每次合并時(shí)都增加rank。錯(cuò)誤示例if (rank[rootX] rank[rootY]) { parent[rootX] rootY; rank[rootY]; // 錯(cuò)誤只有高度相等時(shí)才需要增加 }后果這會(huì)導(dǎo)致rank不再真實(shí)反映樹的高度破壞了按秩合并的平衡性可能使樹高增長(zhǎng)快于預(yù)期。牢記原則只有當(dāng)兩棵樹高度嚴(yán)格相等時(shí)將一棵樹作為子樹合并到另一棵才會(huì)使后者的高度增加1。我的模板中rank[rootX]只在else分支即高度相等時(shí)執(zhí)行這是正確的。5.4 忘記判斷“已在同一集合”導(dǎo)致的無限遞歸問題在unite函數(shù)中如果省略了if (rootX rootY) return;這一行。后果當(dāng)合并兩個(gè)已經(jīng)屬于同一集合的元素時(shí)rootX rootY。如果繼續(xù)執(zhí)行下面的合并邏輯在高度相等的情況下代碼parent[rootY] rootX;相當(dāng)于讓根節(jié)點(diǎn)指向自己這沒有問題。但緊接著rank[rootX]會(huì)錯(cuò)誤地增加秩。更嚴(yán)重的是在某些帶權(quán)并查集的實(shí)現(xiàn)中缺少這個(gè)判斷會(huì)導(dǎo)致權(quán)值計(jì)算進(jìn)入死循環(huán)或產(chǎn)生錯(cuò)誤結(jié)果。教訓(xùn)永遠(yuǎn)在unite開始時(shí)判斷根節(jié)點(diǎn)是否相同。這是一個(gè)低成本的安全檢查。5.5 性能排查如何知道你的并查集是否高效當(dāng)你懷疑自己的并查集性能有問題時(shí)可以添加簡(jiǎn)單的調(diào)試代碼統(tǒng)計(jì)find調(diào)用次數(shù)與平均遞歸深度/迭代次數(shù)在find函數(shù)內(nèi)加一個(gè)靜態(tài)計(jì)數(shù)器。在程序結(jié)束后輸出總調(diào)用次數(shù)和平均每次查找訪問的父節(jié)點(diǎn)數(shù)。在優(yōu)化良好的并查集中平均訪問次數(shù)應(yīng)該是一個(gè)非常小的常數(shù)接近2或3?？梢暬瘶浣Y(jié)構(gòu)用于小規(guī)模調(diào)試寫一個(gè)輔助函數(shù)打印出所有節(jié)點(diǎn)的父節(jié)點(diǎn)關(guān)系。檢查是否出現(xiàn)了明顯的長(zhǎng)鏈。這對(duì)于理解合并過程和學(xué)習(xí)算法非常有幫助。6. 模板的變體與性能對(duì)比除了經(jīng)典實(shí)現(xiàn)了解其他變體有助于你在特定場(chǎng)景下做出最佳選擇。6.1 基于大小的合并 (Union by Size)如前所述將rank數(shù)組替換為size數(shù)組在合并時(shí)總是將小集合合并到大集合。優(yōu)點(diǎn)可以O(shè)(1)時(shí)間獲取每個(gè)集合的大小。同樣能保證樹高為O(log n)。缺點(diǎn)對(duì)樹高的控制略遜于按高度合并但理論復(fù)雜度相同。對(duì)于不需要集合大小信息的場(chǎng)景按高度合并是更經(jīng)典的選擇。選擇建議如果問題需要頻繁查詢連通塊大小選這個(gè)變體。否則用按高度合并。6.2 非遞歸路徑壓縮 按秩合并如前所述迭代版find函數(shù)。優(yōu)點(diǎn)絕對(duì)避免遞歸棧溢出風(fēng)險(xiǎn)。缺點(diǎn)代碼稍長(zhǎng)可讀性略差。選擇建議在嵌入式環(huán)境或?qū)？臻g極度敏感的場(chǎng)景下使用。一般情況用遞歸版即可。6.3 僅路徑壓縮 or 僅按秩合并理論上同時(shí)使用兩種優(yōu)化才能達(dá)到最優(yōu)的均攤時(shí)間復(fù)雜度阿克曼函數(shù)的反函數(shù)近乎常數(shù)。但實(shí)踐中僅路徑壓縮find操作很快但如果不小心形成了深樹合并操作可能較慢。不過由于路徑壓縮的存在壞結(jié)構(gòu)很快會(huì)被壓平。僅按秩合并樹的結(jié)構(gòu)始終比較平衡find操作穩(wěn)定在O(log n)。結(jié)論對(duì)于時(shí)間要求苛刻的場(chǎng)景務(wù)必同時(shí)使用兩者。這是經(jīng)過充分驗(yàn)證的最佳實(shí)踐。6.4 內(nèi)存優(yōu)化使用原生數(shù)組和靜態(tài)大小如果問題規(guī)模N在編譯期或初期就已知且固定可以使用原生數(shù)組int parent[N]和int rank[N]。優(yōu)點(diǎn)稍微減少一點(diǎn)vector容器帶來的開銷訪問可能更快。缺點(diǎn)失去靈活性。選擇建議在性能瓶頸分析明確指向并查集容器開銷時(shí)這非常罕見才考慮此優(yōu)化。99%的情況下vector是更優(yōu)選擇。最后關(guān)于這個(gè)自用模板我個(gè)人最深刻的體會(huì)是理解遠(yuǎn)比記憶重要。你不僅要會(huì)套用模板更要清楚每一行代碼為何這樣寫尤其是路徑壓縮和按秩合并的細(xì)節(jié)。在緊張的競(jìng)賽或調(diào)試中一個(gè)細(xì)微的誤解就可能導(dǎo)致難以察覺的錯(cuò)誤。我建議你在理解的基礎(chǔ)上親手將這個(gè)模板敲幾遍用不同的測(cè)試用例包括自環(huán)、重復(fù)邊、隨機(jī)大數(shù)據(jù)去驗(yàn)證它并嘗試實(shí)現(xiàn)它的幾個(gè)變體。當(dāng)你對(duì)它了如指掌時(shí)它才能真正成為你解決連通性問題的可靠武器。