🚀 并查集（Union-Find）詳解：原理、實現與優化
并查集（Union-Find）是一種非常高效的數據結構，用于處理動態連通性問題，即判斷若干個元素是否屬于同一個集合，并支持集合合并操作。它在圖算法中（如 Kruskal 最小生成樹）、朋友圈統計、網絡連通性判斷等場景中非常常見。
🧠 并查集的核心功能
- find(x)：查找元素
x所在集合的代表（也叫“根節點”） - union(x, y)：將元素
x和y所在的兩個集合合并 - parent[x]：記錄每個元素的“父親”，通過父親鏈條找祖先（樹結構）
🧩 并查集基本結構
n = 5
parents = list(range(n + 1)) # parents[i] = i，0號位不使用
🔍 基本實現：find 和 union
def find(x):if parents[x] == x:return xelse:return find(parents[x])
def union(x, y):root_x = find(x)root_y = find(y)if root_x == root_y:return Falseparents[root_y] = root_xreturn True
🧠 類比記憶
- 每個元素的
parent就像是它的“爸爸” find(x)就是往上找老祖宗union(x, y)就是兩個家族聯姻，把一個家族并進另一個
? 并查集優化技巧（路徑優化）：路徑壓縮優化
查詢時順便把路徑上所有的節點都指向大族長，一次find后這條路徑的深度為1
def find(x):if x != parents[x]:parents[x] = find(parents[x])return parents[x]
🧱 并查集優化技巧（合并優化）：按秩合并 & 按大小合并
🔢 按大小合并（Union by Size）
小家族歸大家族，大的當族長
size = [1] * (n + 1)def union(x, y):rx, ry = find(x), find(y)if rx == ry:return Falseif size[rx] < size[ry]:parents[rx] = rysize[ry] += size[rx]else:parents[ry] = rxsize[rx] += size[ry]return True
🏷? 按秩合并（Union by Rank）
輩分高的當族長
rank = [0] * (n + 1)def union(x, y):rx, ry = find(x), find(y)if rx == ry:return Falseif rank[rx] < rank[ry]:parents[rx] = ryelif rank[rx] > rank[ry]:parents[ry] = rxelse:parents[ry] = rxrank[rx] += 1return True
💡 組合使用建議
最推薦的并查集配置是：
路徑壓縮 + 按秩合并 或 按大小合并
能達到幾乎 O(1) 的查詢和合并效率。
📚 應用場景
- Kruskal 最小生成樹算法
- 網絡連通性判斷
- 動態連通塊個數統計
- 島嶼數量（LeetCode 200）
- 冗余連接（LeetCode 684）
- 朋友圈數量（LeetCode 547）
🎯 總結
| 術語 | 含義 |
|---|---|
find(x) | 找出 x 所屬集合的根節點 |
union(x, y) | 合并 x 和 y 的集合（若不屬于同一集合） |
| 路徑壓縮 | 加快 find 查詢效率 |
| 按秩/按大小 | 優化合并策略，防止退化 |
| 樹的結構 | 集合之間的連接關系 |
并查集看起來簡單，背后其實是極高效的數據結構設計。建議掌握它，并嘗試應用到圖論、集合問題中去！
🧩 常見練習題
? 基礎入門題
| 題號 | 題目名稱 | 鏈接 | 簡介 |
|---|---|---|---|
| 200 | 島嶼數量 | LeetCode 200 | 判斷二維網格中有多少個連通塊 |
| 684 | 冗余連接 | LeetCode 684 | 找出圖中導致環的邊 |
| 1319 | 連通網絡的操作次數 | LeetCode 1319 | 判斷有多少連通塊，以及最少連接次數 |
🧠 中級應用題
| 題號 | 題目名稱 | 鏈接 | 簡介 |
|---|---|---|---|
| 1202 | 交換字符串中的元素 | LeetCode 1202 | 使用并查集形成交換組，對組內排序 |
| 721 | 賬戶合并 | LeetCode 721 | 通過郵箱合并屬于同一用戶的賬戶 |
| 323 | 無向圖中連通分量的數目 | LeetCode 323 | 通用連通塊計數問題 |
🔍 進階與變種題
| 題號 | 題目名稱 | 鏈接 | 簡介 |
|---|---|---|---|
| 399 | 除法求值 | LeetCode 399 | 帶權并查集：維護節點之間的比例關系 |
| 547 | 省份數量（等價朋友圈問題） | LeetCode 547 | 判斷有多少朋友圈/省份 |
| 990 | 等式方程的可滿足性 | LeetCode 990 | 并查集維護等式約束 |
📌 推薦練習順序
200- 島嶼數量684- 冗余連接1319- 連通網絡的操作次數547- 省份數量1202- 字符串交換721- 郵箱合并399- 除法求值990- 等式方程可解性
🧠 建議掌握：
- 基礎并查集結構（
find,union） - 路徑壓縮優化
- 帶權并查集（維護差值、比例等信息）
- 一維映射（如坐標 → 編號）
