## 並查集 Disjoint Set
[例題](https://judge.cchs.chc.edu.tw/ShowProblem?problemid=a531)
:::info
註 : 並查集有很多種寫法，這邊介紹的是我常用的寫法。
可以看看網路上面是怎麼教的。
https://oi-wiki.org/ds/dsu/
https://hackmd.io/@CLKO/rkRVS_o-4
:::
又稱互斥集或$DSU$，具有下列功能的資料結構。
> 所有元素 $P$ 編號為 $1,2,3,...,n$。
> 1. 對於$P$中的每個元素$t$都恰有一個集合包含該元素。
> 2. 把$A$,$B$兩個元素所在的集合合併到同個集合中。
> 3. 查詢$A$,$B$兩個元素所在的集合是否是同一個集合。
>
由於 $STL$ 並沒有支援所有我們需要自己實作，值得慶幸的是，這個資料結構實作比較輕鬆。

並查集 範例 :

1. 首先，我們需要紀錄每個元素的 $Boss$ ，每個元素的 $Boss$ 一開始都是自己，如果一個元素的 $Boss$= 該元素，那這個元素我們就定義它是最大的 $Boss$。
2. 如果需要判斷兩個元素是否在同一個集合，可以判斷兩個元素的最大的 $Boss$ 是否相同。
3. 如果要合併兩個集合，就把其中一個元素的最大的 $Boss$ 指定為另外一個元素最大的的 $Boss$ 。

範例 :

#include<bits/stdc++.h>
using namespace std;
const MAXN=2e5+5;
vector<int> boss(MAXN, 0);
void build_dsu() {
    for(int i=1;i<MAX;i++) boss[i]=i;
}
int find(int now) {
    if(boss[now]==now) return now;
    return find(boss[now]);
}
bool same(int x, int y) {
    return find(x)==find(y); 
}
void union(int x, int y) {
    int fx=find(x), fy=find(y);
    boss[fx]=fy;
}

這個程式的每次操作的時間複雜度是$O(n)$，因為可以觀察到查詢跟合併的操作都是依靠$find()$這個函式，而一個元素要找到它最大的$boss$最多需要執行$n$次，因此整體的時間複雜度式$O(Qn)$，$Q$是總共有幾次操作。
因此我們可以針對$find()$函式進行優化，我們可以發現一個元素的$Boss$的$Boss$一直到這個元素的最大的$Boss$之前，所有的$Boss$的最大的$Boss$都是相同的，因此我們可以把$find()$改成下面的程式，看起來差不多，但是每次查詢的時間複雜度根據均攤分析可以優化到$O(logn)$，這個優化我們稱之為路徑壓縮。
* [維基百科](https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity)
* [OI Wiki](https://oi-wiki.org/ds/dsu/)

int find(int now) {
    if(boss[now]==now) return now;
    return boss[now]=find(boss[now]);
}

快還要更快，一個很貪心且直覺的想法就是在合併兩個集合的時候，把比較小的集合的最大的$Boss$，設成比較大的集合的最大的$Boss$，一定比把比較大的集合的最大的$Boss$，設成比較小的集合的最大的$Boss$，因為很顯然的，比較大的集合在更新的最大的$Boss$時需要更多時間，因為元素更多，這樣可以把每次操作的時間優化成$O(\alpha(n))$。
> $\alpha(n)$，的中文是反阿克曼函數，增長很慢，比較直觀的是:$\alpha(2^{2^{2^{2^2}}})=4$，$2^{2^{2^{2^2}}}\approx 2\times10^{19728}$

$DSU .final$

#include<bits/stdc++.h>
using namespace std;
const MAXN=2e5+5;
vector<int> boss(MAXN, 0), sz(MAXN, 1); //一開始的集合大小都是1
void build_dsu() {
    for(int i=1;i<MAX;i++) boss[i]=i;
}
int find(int now) {
    if(boss[now]==now) return now;
    return boss[now]=find(boss[now]);
}
bool same(int x, int y) {
    return find(x)==find(y); 
}
void union(int x, int y) {
    int fx=find(x), fy=find(y);
    if(sz[fx]<sz[fy]) swap(fx, fy);
    sz[fx]+=sz[fy];
    boss[fy]=boss[fx];
}

練習題
> [DSU](https://atcoder.jp/contests/abc177/tasks/abc177_d)
> [DSU](https://cses.fi/problemset/task/1676/)