Submission #11592748

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int INF = 100000;
typedef pair<int,int> P;


class UnionFind{
public:
    vector<int> par;
    vector<int> rank;

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

    int find(int x){
        if (par[x] == x) return x;
        else return par[x] == find(par[x]);
    }

    void unite(int x,int y){
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) par[x] = y;
        else {
            par[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
    }

    bool same(int x,int y){
        return find(x) == find(y);
    }
};

int main() {
    int N,Q;cin >> N >> Q;

    UnionFind uf(N);
    for (int i = 0;i < Q;i++){
        int p,a,b;cin >> p >> a >> b;
        if (p == 0){
            uf.unite(a,b);
        }
        else{
            if (uf.same(a,b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}

Submission Info

Judge Result