verify/unionfind.test.cpp

View this file on GitHub
Last update: 2019-12-04 00:43:23+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

lib/classes/unionfind.cpp

Code

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

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

#include "../lib/classes/unionfind.cpp"


signed main() {

    int n, q;
    scanf("%d%d", &n, &q);
    vector<int> t(q), u(q), v(q);
    for(int i = 0; i < q; ++i)
        cin >> t[i] >> u[i] >> v[i];

    UnionFind uf(n);
    for(int i = 0; i < q; ++i){
        if(t[i] == 0)
            uf.Unite(u[i], v[i]);
        else
            cout << (uf.Find(u[i]) == uf.Find(v[i])) << endl;
    }
}

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

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

#line 1 "lib/classes/unionfind.cpp"
struct UnionFind{
    vector<int> par;
    int count;
    UnionFind(int n) : par(n, -1), count(0){}
    int Find(int x){return par[x] < 0 ? x : Find(par[x]);}
    int Size(int x){return par[x] < 0 ? -par[x] : Size(par[x]);}
    bool Unite(int x, int y){
        x = Find(x);
        y = Find(y);
        if(x == y)
            return false;
        if(par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return ++count;
    }
};

#line 8 "verify/unionfind.test.cpp"


signed main() {

    int n, q;
    scanf("%d%d", &n, &q);
    vector<int> t(q), u(q), v(q);
    for(int i = 0; i < q; ++i)
        cin >> t[i] >> u[i] >> v[i];

    UnionFind uf(n);
    for(int i = 0; i < q; ++i){
        if(t[i] == 0)
            uf.Unite(u[i], v[i]);
        else
            cout << (uf.Find(u[i]) == uf.Find(v[i])) << endl;
    }
}