# 併查集 Disjoint Set (Union-Find)
我們常用的資料結構無非就幾種操作: 插入、查詢、合併，差別只在於需要維護的對象有誰
併查集又稱為不相交集合、互斥集，用於維護一堆集合，是個非常有效率的工具。在檢查[連通分量 (連通單元/成分/塊)](https://hackmd.io/@ShanC/connected_component)，亦或是尋找一張圖的最小生成樹都是一個重要的存在
在此章節，要維護的東西是一個集合，因此需要先說明集合的性質
## 集合 Sets
**這裡只討論併查集用的到的集合概念**
- 一個集合 $S$ 中，會由許多元素(element) $x$ 組成
- 若 $x$ 是 $S$ 的元素，則可以寫作 $x \in S$
- 可用大括號表示集合: $S=\{1,2,3\}, G=\{4,5,6\}$
- 兩個集合可以使用聯集 (Union) 來合併: $S\cup G=\{1,2,3,4,5,6\}$
- 集合沒有順序
- 同一元素就算合併多次也只會寫一次: $\{1,2,3,1\}=\{1,2,3\}$
- 一個集合的元素個數稱為基數 (Cardinal number)，寫作 $|S|$
- $\emptyset$ 為空集合的符號，若 $S=\emptyset$，則 $|S|=0$
## 併查集實作
### 簡介
此資料結構共有三種操作 (operation) : 初始化、查詢所在集合、合併
某種程度上，併查集也算一種樹狀資料結構
### 需要維護的東西
此資料結構需要維護一個陣列 $f[i]$ 用於紀錄 $i$ 的父親是誰
我們可以用樹狀結構的根節點來作為一個集合的代表
由於根節點並沒有父親，因此可以把根節點的父親指向自己 $f[root]=root$
### 初始化
在併查集，每一個元素一開始都是**自己的集合**
假設有 $n$ 個元素，則需要將編號 $1$ ~ $n$ 的節點連向自己
```cpp
void init(n){ // 初始化
f.resize(n);
for (int i = 1; i <= n; i++) {
f[i] = i;
}
}
```
<center>
<img src="https://hackmd.io/_uploads/HyJZTtx7Jg.png" style="margin: 0 auto; display: block; width: 250px">
</center>
### 查詢所在集合
由於是樹狀資料結構，可以用遞迴來尋找元素屬於哪一個集合
```cpp
int find(int x){
if (f[x] == x) // 如果當前節點為 f[x] == x
return x; // 則為根節點
return find(f[x]);
}
```
### 合併
合併可以將兩個集合聯集在一起
步驟如下:
1. 丟入兩參數 $x$ 和 $y$
2. 尋找 $x$ 和 $y$ 所在的集合 (找代表元素)
3. 如果 $x$ 和 $y$ 在不同集合，就用其集合的代表元素來合併
```cpp
void merge(int x, int y) { // 合併 x, y 所在集合
x = find(x); // x 找到其根節點
y = find(y); // y 找到其根節點
if(x != y) // 如果 x,y 原本就屬於同一個集合則不需合併
f[y] = x; // 將其中一個根節點連到另一個
}
```
`union` 在 C++ 是關鍵字，在此使用 `merge` 作為代替
<center>
<img src="https://hackmd.io/_uploads/HyahW5x7kg.png" style="margin: 0 auto; display: block; width: 550px">
</center>
## 併查集的限制與優化
### 限制
透過上述這種合併方式，很有可能連出一條鏈(chain)，如果從鏈的非根終點查詢所在集合，則有可能會需要走訪所有節點，花費太多時間。因此可以考慮以下兩種優化方式
<center>
<img src="https://hackmd.io/_uploads/HkYus5eQkx.png" style="margin: 0 auto; display: block; width: 300px">
</center>
### 優化1: 啟發式合併 Union by Rank
可以多花一個陣列的空間，維護每個集合的大小關係 $sz[~]$
由於一開始每個集合都是自己，因此初始化大小為 $1$
```cpp
void init(int n){ // 初始化
for (int i = 1; i <= n; i++) {
f[i] = i;
sz[i] = 1;
}
}
```
在每一次合併當中，將小的集合併入大的集合
```cpp
void merge(int x, int y) { // 將 x 和 y 合併
x = find(x), y = find(y);
if (x == y)
return;
if (sz[x] < sz[y]) // 將小的併入大的
swap(x, y);
sz[x] += sz[y];
f[y] = x;
}
```
設有 $n$ 個元素，在最差情況下，只需要搜尋 $log_2(n)$ 左右個元素，即可找到根節點
<center>
<img src="https://hackmd.io/_uploads/HkOPp5gQkl.png" style="margin: 0 auto; display: block; width: 400px">
</center>
### 優化2. 路徑壓縮 Path Compression
將所有節點都指向根節點 (即代表元素)，每次查詢只需要花一個步驟就能找到根節點
```cpp
int find(int x){
if (f[x] == x) // 如果當前節點為 f[x] == x
return x; // 則為根節點
f[x] = find(f[x]);
return f[x];
}
```
<center>
<img src="https://hackmd.io/_uploads/By0i0ceX1g.png" style="margin: 0 auto; display: block; width: 350px">
</center>
### 兩種優化都使用的程式碼
```cpp
int f[MAXN], sz[MAXN];
void init(int n){ // 初始化
for (int i = 1; i <= n; i++) {
f[i] = i;
sz[i] = 1;
}
}
int find(int x){
if (f[x] == x) // 如果當前節點為 f[x] == x
return x; // 則為根節點
f[x] = find(f[x]);
return f[x];
}
void merge(int x, int y) { // 將 x 和 y 合併
x = find(x), y = find(y);
if (x == y)
return;
if (sz[x] < sz[y]) // 將小的併入大的
swap(x, y);
sz[x] += sz[y];
f[y] = x;
}
```
## 時間複雜度
### 分析優化的時間複雜度
因併查集是一種樹狀資料結構，設 $h$ 為樹高，$n$ 為元素個數
- 啟發式合併
- 初始化: $O(n)\times 2=O(n)$
- 查詢所在集合: $O(h) = O(log ~n)$
- 合併: $O(h)\times 2 + O(1)=O(h) = O(log ~n)$
- 路徑壓縮
- 初始化: $O(n)$
- 查詢所在集合: $O(1)$
- 合併: $O(1)\times 2 + O(1)=O(1)$
- 兩種優化一起用
- 初始化: $O(n)$
- 查詢所在集合: $O(\alpha(n))\approx O(1)$
- 合併: $O(\alpha(n)) \times 2 + O(1)\approx O(1)$
其中，$\alpha(n)$ 是一個成長非常快的迭代的函數 $A_k(n)$ 的反函數。簡而言之就是 $\alpha(n)$ 成長非常緩慢，就算將宇宙所有的原子數量 $10^{80}$ 代入，$\alpha(10^{80}) \leq 4$，所以幾乎可以算是常數
詳細證明: https://codeforces.com/blog/entry/98275
~~我的原文書花了 $9$ 頁在探討這個問題，而我只看得懂結論 XD~~
## 題目練習
[Zerojudge f677. FJCU_109_Winter_Day3_Lab1 並查集練習](https://zerojudge.tw/ShowProblem?problemid=f677)
[Zerojudge a445. 新手訓練系列- 我的朋友很少](https://zerojudge.tw/ShowProblem?problemid=a445)
[CSES Counting Rooms](https://cses.fi/problemset/task/1192/)
[Zerojudge j243. 111北二2a.資料分組問題](https://zerojudge.tw/ShowProblem?problemid=j243)
[Zerojudge f260. 愛八卦的同學](https://zerojudge.tw/ShowProblem?problemid=f260)
[Zerojudge d831. 畢業旅行](https://zerojudge.tw/ShowProblem?problemid=d831)
[Zerojudge f292. 11987 - Almost Union-Find](https://zerojudge.tw/ShowProblem?problemid=f292)
[Zerojudge g212. E.魔法集合（set）](https://zerojudge.tw/ShowProblem?problemid=g212)
[Zerojudge f310. 10158 - War](https://zerojudge.tw/ShowProblem?problemid=f310)
[Zerojudge c291. APCS 2017-0304-2小群體](https://zerojudge.tw/ShowProblem?problemid=c291)
[Zerojudge g598. APCS 4. 真假子圖](https://zerojudge.tw/ShowProblem?problemid=g598)
[CSES Road Construction](https://cses.fi/problemset/task/1676)
[Codeforces 2184E. Exquisite Array](https://codeforces.com/contest/2184/problem/E)
----
## 參考資料
- Introduction to Algorithms, Fourth Edition
- [維基百科](https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0_(%E6%95%B0%E5%AD%A6))
- [海大競程講義 Graph Theory & DSU](https://hackmd.io/@LeeShoWhaodian/2024I2CP_DSUandGraph#/2)
- [set 台師大演算法筆記](https://web.ntnu.edu.tw/~algo/Set.html)
- [圖論演算法ch21 — DS for Disjoint Sets - 慈慈 - Medium](https://cihcih.medium.com/%E5%9C%96%E8%AB%96%E6%BC%94%E7%AE%97%E6%B3%95ch21-ds-for-disjoint-sets-de61210d671a)
- [Codeforces Proving the inverse Ackermann complexity of Union-Find](https://codeforces.com/blog/entry/98275)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2024/11/24
Sign in with Wallet
Connect another wallet