標籤: disjointSets

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

class dsu{
    private:
        vector<int> p;
        vector<long long> rank;
    public:
        void init(int n){
            for(int i=0;i<=n;i++){
                p.push_back(i);
                rank.push_back(1);
            }
        }
        
        int find(int a){
            if(a==p[a]) return a;
            return p[a]=find(p[a]);
        }
        
        bool same(int a,int b){
            return find(a)==find(b);
        }
        
        bool uni(int a,int b){
            if(!same(a,b)){
                int rA=rank[find(a)],rB=rank[find(b)];
                if(rA>rB){
                    p[find(b)]=p[find(a)];
                }else if(rA==rB){
                    p[find(b)]=p[find(a)];
                    rank[p[find(a)]]++;
                }else{
                    p[find(a)]=p[find(b)];
                }
            }
        }
};