Submission #7122916

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

struct union_find_tree{
    vector<ll> par;
    vector<ll> rank;
    union_find_tree(ll n){
        for(ll i=0;i<n;i++){
            par.push_back(i);
            rank.push_back(0);
        }
    }

    ll find(ll a){
        if(par[a]==a)return a;
        return find(par[a]);
    }

    void unite(ll a,ll b){
        ll root_a=find(a);
        ll root_b=find(b);
        if(root_a==root_b)return;
        if(rank[root_a]<rank[root_b]){
            par[root_a]=root_b;
        }else if(rank[root_a]>rank[root_b]){
            par[root_b]=root_a;
        }else{
            par[root_a]=root_b;
            rank[root_a]++;
        }
    }

    bool same(ll a,ll b){
        return find(a) == find(b);
    }

};

int main(){
    ll n,q;
    cin>>n>>q;
    union_find_tree uft(n);
    rep(i,q){
        ll p,a,b;
        cin>>p>>a>>b;
        if(p==0){
            uft.unite(a,b);
        }else{
            if(uft.same(a,b)){
                cout<<"Yes"<<endl;
            }else{
                cout<<"No"<<endl;
            }
        }
    }
}

Submission Info

Judge Result