# 并查集
## 定義
并查集是一種維護集合的數據結構，支持「合并」和「查找」兩種操作，可用數組實現。
### 數據結構
```C++
// father[i] 表示元素 i 的父親節點
// 同一個并查集只有一個根節點
int father[N];
```
## 基本操作
### 初始化
```C++
for(int i=1;i<=N;i++){
father[i]=i; // 令 father[i]=-1 也可
}
```
### 查找
```c++
// 返回 x 所在并查集的根節點
int findFather(int x){
while(x!=father[x]){
x=father[x];
}
return x;
}
```
### 合并
```c++
void Union(int a, int b){
int faA=findFather(a);
int faB=findFather(b);
if(faA!=faB) father[faA]=faB;
}
```
## 路徑壓縮
```C++
int findFather(int x){
int a=x;
while(x!father[x]){
x=father[x];
}
// 把路徑上經過的所有節點的父親節點都改為根節點
while(a!=father[a]){
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
```
