# 並查集union find

> https://zerojudge.tw/ShowProblem?problemid=a445

* 處理disjoint set(有向圖)
* disjoint set - 互不相連的群組，ex下圖

> (https://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Disjoint_sets.svg/330px-Disjoint_sets.svg.png)
1. 初始個點指向自己
2. find() - 查詢元素屬於哪個集合
* 找到自己指向的元素，直到自己指向的是自己，就是那一組disjoint set的代表
* ex: p[5]=2, p[2]=1, p[1]=1 -> return 1
* 可以邊查詢邊壓縮路徑，縮短後續查詢時間
4. union() - 將兩個子集合合併為一個集合
* 將代表元素指向另一個代表元素

find:

int Find(int x){
    if(p[x]==x) return x;
    return Find(p[x]);
}

find(路徑壓縮):

int Find(int x){
    if(p[x]==x) return x;
    return p[x]=Find(p[x]);
}

union:

void Union(int x,int y){
    int g1 = Find(x);
    int g2 = Find(y);
    p[g2] = g1;
}

**可連帶查詢集合的成員數目**:
(預設p[i]為-1，代表指向自己)

int Find(int x){    
    return p[x] < 0 ? x : p[x] = Find(p[x]);
}

void Union(int x, int y){
    int g1 = Find(x);
    int g2 = Find(y);
    if(g1 != g2){
        p[g1] += p[g2]; //add amount of two set together
        p[g2] = g1; // set only g1 to represent the amount
    }
}

把點獨立出來
---

https://zerojudge.tw/ShowProblem?problemid=d449

* 用帶有集合成員數的並查集
* find, union操作一樣，並另外建一個index陣列存每個元素對應到並查集的位置
* 每當要獨立出一個點x，就對並查集陣列新增一個元素(預設-1)，並把index[x]更新為並查集最新新增的位置。（原本點x的根所存的成員數也要減一）
* 所以原本點x所指向並查集的位置就如同不存在了，但是原先點x所在的集合一樣維持相連（除了點x）。

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

vector<LL> arr, ind;// arr is dsu array, ind is the map of each element

LL fd(LL x){
    if(arr[x]<0) return x;
    return arr[x]=fd(arr[x]);
}

void un(LL x, LL y){
    LL g1=fd(x), g2=fd(y);
    if(g1!=g2){
        arr[g1]+=arr[g2];
        arr[g2]=g1;
    }
}

// separation
void sep(LL x){
    arr.EB(-1);
    ind[x]=arr.size()-1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    LL n, m, x, y, a;
    while(cin>>n>>m){
        arr.resize(n);
        ind.resize(n);
        rep(i,0,n) arr[i]=-1, ind[i]=i;
        rep(i,0,m){
            cin>>a;
            if(a==1){
                cin>>x>>y;
                x--, y--;
                // fd傳入ind[x](x之對應位置)
                if(fd(ind[x])!=fd(ind[y])){
                    un(ind[x], ind[y]);
                    n--;
                }
            }
            else{
                cin>>x;
                x--;
                LL f=fd(ind[x]);
                // 如果這個集合只有自己一個，那它已經是獨立的了
                if(arr[f]!=-1){
                    arr[f]++;// value is negative so add one to represent minus one
                    sep(x);
                    n++;
                }
            }
        }
        cout << n << NL;
    }
}

啟發式合併

int ar[1000010];

int get(int x){
	if(ar[x]<0) return x;
	return ar[x]=get(ar[x]);
}

void mrg(int x, int y){
	x=get(x), y=get(y);
	if(ar[x]<ar[y]) swap(x, y);
	ar[y]+=ar[x];
	ar[x]=y;
}

dsu with rollback

int dsu[500010], sz[500010], cnt;
vector<pair<int*,int>> sts;
vector<int> stp;

int get(int x){
	while(dsu[x]!=x) x=dsu[x];
	return x;
}

void mrg(int a, int b){
	a=get(a), b=get(b);
	if(sz[a]<sz[b]) swap(a, b);
	stp.push_back(b);
	sts.push_back({&sz[a], sz[a]});
	sz[a]+=sz[b];
	dsu[b]=a;
}

void undo(){
	dsu[stp.back()]=stp.back();
	*sts.back().f=sts.back().s;
	stp.pop_back();
	sts.pop_back();
}