Union-Find

1 基本概念

并查集是一種用于處理集合合并與查詢的數據結構，主要用于解決：

• 判斷兩個元素是否屬于同一個集合
• 合并兩個集合
• 圖的連通性問題（如 Kruskal 最小生成樹、島嶼數量、等價類問題）

核心思想：每個元素初始是一個獨立的集合（自成一個樹的根）。使用兩個操作：

1. find(x)：查找元素 x 所在集合的代表元（根）
2. union(x, y) / unite(x, y)：將元素 x 和 y 所在的兩個集合合并為一個

1.1 Find(x) - 查詢操作

• 找出元素 x 所在集合的代表元（也叫根節點、父節點）
• 判斷兩個元素是否屬于同一個集合：只需比較它們的代表元是否相同

1.2 Union(x, y) - 合并操作

• 將元素 x 和 y 所在的兩個集合合并
• 目的是把兩個集合的元素歸于同一個集合（也就是連通）

并查集的本質：將多個不相交的集合合并，并在查詢時保持高效

---

2 并查集的結構和優化

2.1 數據結構設計

• parent[i]：表示第 i 個元素的父節點（初始時每個元素是自己的父親）

• 常見擴展字段：

  • rank[i]：節點的秩（可以理解為樹的高度或大小，用于優化合并）
  • size[i]：集合的大小（如果你需要追蹤每個集合的元素個數）

---

2.2 兩大優化策略（關鍵）

2.2.1 路徑壓縮（Path Compression）

• 優化 find(x) 操作
• 將 x 到根節點路徑上的所有節點直接指向根，降低后續查找的復雜度
• 時間復雜度近似 O(α(n))，α 是反阿克曼函數，幾乎是常數

int find(int x) {if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];
}

• 每次查詢時，將 x 的所有祖先直接掛到根節點，形成扁平結構
• 減少下次查找路徑長度

2.2.2 按秩合并（Union by Rank or Size）

• 合并時，總是將“較矮”的樹合并到“較高”的樹，保持整體平衡，防止鏈式退化

void union(int x, int y) {int px = find(x), py = find(y);if (px == py) return;if (rank[px] < rank[py])parent[px] = py;else if (rank[px] > rank[py])parent[py] = px;else {parent[py] = px;rank[px]++;}
}

---

3 使用并查集的注意事項

注意事項	說明
初始化	每個元素一開始是自己的父節點（parent[i] = i）
找代表元要用 find()	不要直接比較 parent[x] == parent[y]，必須比較 find(x) == find(y)
使用路徑壓縮	提高查找效率，避免變成鏈表結構
合并要檢查代表元	避免重復合并或死循環
不適合有環結構查詢	并查集不能表示通用圖（除非用于檢測是否成環）
不支持高頻動態插入刪除	并查集適合處理固定集合或批量問題，不適合頻繁插入刪除

---

4 典型應用場景

并查集廣泛應用于以下場景：

4.1 判斷連通性

• 無向圖中判斷兩個點是否連通
• 例題：LeetCode 547. 省份數量（朋友圈）

4.2 等價類/合并集合

• 把多個元素按關系合并為“集合組”
• 例題：LeetCode 1061. 按字典序排列的最小等價字符串

4.3 檢測環路（圖中是否有環）

• 并查集用于無向圖的成環檢測
• 例題：Kruskal 最小生成樹（MST）

4.4 島嶼問題/連通區域

• 將二維網格中相鄰的“陸地”用并查集合并，統計島嶼數
• 例題：LeetCode 200. 島嶼數量

4.5 網絡連接問題

• 網絡中節點是否連通、連接多少次才能連通
• 例題：LeetCode 1319. 連通網絡的操作次數

---

5 實現模板

class UnionFind {
private:vector<int> parent;vector<int> rank;  // 或者 sizepublic:UnionFind(int n) {parent.resize(n);rank.resize(n, 1);iota(parent.begin(), parent.end(), 0); // parent[i] = i}// 查找根節點，并進行路徑壓縮int find(int x) {if (parent[x] != x)parent[x] = find(parent[x]); // 路徑壓縮return parent[x];}// 合并兩個集合void unite(int x, int y) {int px = find(x);int py = find(y);if (px == py) return;// 按秩合并if (rank[px] < rank[py]) {parent[px] = py;} else if (rank[px] > rank[py]) {parent[py] = px;} else {parent[py] = px;rank[px]++;}}// 判斷兩個元素是否在同一個集合bool connected(int x, int y) {return find(x) == find(y);}
};

6 問題示例：合并等價字符集合（字典序最小）

當我們想用并查集維護字符集合時，可以做如下改造：

• parent[26]：表示字符 ‘a’ 到 ‘z’ 的父節點
• 合并時總是把字典序較小的字符作為根，這樣找出的代表字符就是該等價類的最小字母

class Solution {
public:string smallestEquivalentString(string s1, string s2, string baseStr) {vector<int> parent(26);iota(parent.begin(), parent.end(), 0); // a-z 的并查集// 路徑壓縮查找function<int(int)> find = [&](int x) {if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];};// 合并兩個字符等價類，保留字典序較小的作為代表auto unite = [&](int x, int y) {int px = find(x);int py = find(y);if (px == py) return;if (px < py)parent[py] = px;elseparent[px] = py;};for (int i = 0; i < s1.length(); ++i) {unite(s1[i] - 'a', s2[i] - 'a');}string res;for (char c : baseStr) {res += (char)(find(c - 'a') + 'a');}return res;}
};

7 總結

問題特征	是否適合使用并查集
不相交集合合并	非常適合（核心用途）
判斷兩個元素是否屬于同一集合	非常高效
圖的連通性/聚類問題	適合
頻繁增刪元素	不適合，建議用更復雜的數據結構
要維護復雜屬性（如路徑）	不適合

操作	說明	時間復雜度
find(x)	查找 x 所在集合的代表元	O(α(n))
unite(x,y)	合并兩個集合	O(α(n))
connected(x,y)	判斷是否在同一集合	O(α(n))

由于路徑壓縮和按秩合并優化，幾乎所有操作都是近乎常數時間。