Submission #7103450

---

Source Code Expand

#include<iostream>
#include<vector>
using namespace std;
#define rep(i, j, n) for (int i = j; i < n; i++);
typedef pair<int,int>P;

struct UnionFind{
    vector<int> parent;
    vector<int> rank;

    UnionFind(int n) : parent(n),rank(n) {
        for(int i=0;i<n;i++){
            parent[i]=i;
            rank[i]=0;
        }
    }

    int root(int x){
        if(parent[x]==x)return x;
        return parent[x]=root(parent[x]);
    }

    void unite(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry)return ;

        if(rank[rx]<rank[ry])parent[rx]=ry;
        else {
            parent[ry]=rx;
            if(rank[rx]==rank[ry])rank[rx]++;
        }
    }

    bool same(int x,int y){
        int rx=root(x),ry=root(y);
        return rx==ry;
    }
};

int main(){
    int n,q;cin>>n>>q;
    UnionFind uf(n);
    for(int i=0;i<q;i++){
        int p,x,y;
        cin>>p>>x>>y;
        if(p==0)uf.unite(x,y);
        else{
        if(uf.same(x,y))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        }
    }
    return 0;
}

Submission Info

Judge Result