Test/yosupo-judge/UnionFind.test.cpp

View this file on GitHub
Last update: 2021-06-18 21:14:35+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

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

#include"../../Other/Template.cpp"
#include"../../DataStructure/UnionFind.cpp"

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

#line 1 "Test/yosupo-judge/UnionFind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

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

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "DataStructure/UnionFind.cpp"
class UnionFind {
    vector<int> par;
    vector<int> siz;

public:

    UnionFind(int n) {
        par.resize(n);
        siz.resize(n);
        for(int i = 0;i < n;i++) {
            par[i] = i;
            siz[i] = 1;
        }
    }

    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(siz[x] < siz[y]) {
            swap(x,y);
        }
        par[y] = x;
        siz[x] += siz[y];
    }

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

    int size(int x) {
        return siz[find(x)];
    }
};
#line 8 "Test/yosupo-judge/UnionFind.test.cpp"

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