Submission #3819643

---

Source Code Expand

#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl

const ll mod = 1e9 + 7;
const ll inf = 1e18;

void pV(vector<ll> A){
    cout << "[vector]";
    for(int i=0; i<A.size(); i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

// ref
// https://www.slideshare.net/iwiwi/ss-3578491

const int N_MAX = 100010;
int parent[N_MAX];

int findRoot(int x){
    if(parent[x] == x){
        return x;
    }else{
        auto root = findRoot(parent[x]);
        parent[x] = root; // path compression
        return root;
    }
}

// union is reserved word...
void _union(int a, int b){
    auto rootA = findRoot(a);
    auto rootB = findRoot(b);

    if(rootA == rootB){
        return;
    }else{
        parent[a] = b;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    int N, Q;
    cin >> N >> Q;

    // init
    FOR(i, 0, N_MAX){
        parent[i] = i;
    }

    FOR(i, 0, Q){
        int p, a, b;
        cin >> p >> a >> b;

        // union
        if(p==0){
            _union(a, b);
        }
        // find
        else{
            // a & b is same group?
            bool isSameGroup;
            if(findRoot(a) == findRoot(b)){
                isSameGroup = true;
                p("Yes");
            }else{
                isSameGroup = false;
                p("No");
            }
        }
    }
    
    return 0;
}

Submission Info

Judge Result