# Disjoint Set

並查集
用來合併兩個集合

初始化:每個人自己為一個集合

int dis[MAXN];

void init(int N){
    for(int i=1;i<=N;i++) dis[i]=i;
}

查詢:找到root->判斷自己屬於哪個集合

int fa(int id){
    if(dis[id] == id) return id;
    else return fa(dis[id]);
}

壓縮路徑:優化,更新自己的root

int fa(int id){
    if(dis[id] == id) return id;
    else return dis[id] = fa(dis[id]);
}

合併:把b集合合併到a集合

void un(int a,int b){
    a=fa(a);
    b=fa(b);
    dis[b]=a;
}

判斷:判斷是否屬於同一個集合

bool same(int a,int b){
    return fa(a) == fa(b);
}

<a href="https://zerojudge.tw/ShowProblem?problemid=d449">d449: 垃圾信件</a>

#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;

int dis[MAXN],n;
set<int> s[MAXN];  //s[i]裡放的是以i為節點時底下的節點(不包刮自己)

void init(){
    for(int i=1;i<=n;i++){
        dis[i]=i;
        s[i].clear();
    }
}

int fa(int x){
    if(dis[x]==x) return x;
    else{  //路徑壓縮
        s[dis[x]].erase(x);  //把自己在中繼站刪掉
        dis[x]=fa(dis[x]);
        s[dis[x]].insert(x);  //然後新增到root
        return dis[x];
    }
}

int main(){
    cin.sync_with_stdio(0),cin.tie(0);

    int m,a,b,target;
    while(cin >> n >> m){
        init();
        while(m--){
            cin >> target;
            if(target==1){
                cin >> a >> b;
                a=fa(a),b=fa(b);
                if(a==b) continue;
                dis[a]=b;s[b].insert(a);  //Union
            }else{
                cin >> a;
                if(dis[a]==a && s[a].size()==0) continue;  
                //自己為跟節點且沒有子節點代表已經自己一個集合了

                int target,root;  //target為不用新增到root的set的節點
                if(dis[a]==a){                    
                    root=*s[a].begin(); //要轉移的新的跟節點
                    dis[root]=root;  //把新節點的dis設為自己
                    target=root;  //因為節點的set裡不會有自己的節點
                }else{
                    root=fa(a);  //轉移到跟節點
                    s[root].erase(a);  //把a從root裡移除
                    target=a;  //因為a要自己一個dsu所以不能新增到root裡
                }
                for(auto i:s[a]){  //把底下的節點都更新到新的root
                    if(i==target) continue;
                    s[root].insert(i);
                    dis[i]=root;
                }
                dis[a]=a;s[a].clear();  //a為自己一個集合
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(dis[i]==i) ans++;  //計算有幾個root代表有幾個dsu
        }
        cout << ans << '\n';
    }
    return 0;
}