test/union_find.yosupo.unionfind.test.cpp

View this file on GitHub
Last update: 2020-05-09 18:52:06+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

lib/union_find.hpp

Code

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

#include <iostream>
#include "../lib/union_find.hpp"

int main() {
    int n, q; std::cin >> n >> q;
    UnionFind uf(n);
    for (int i = 0; i < q; i++) {
        int t, u, v; std::cin >> t >> u >> v;
        if (t) std::cout << uf.same(u, v) << std::endl;
        else uf.unite(u, v);
    }
    return 0;
}

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

#include <iostream>
#line 1 "lib/union_find.hpp"



#include <vector>

class UnionFind {
public:
    UnionFind(int n) : par(n, -1), ran(n, -1) {}

    void unite(int x, int y) {
        x = find_root(x);
        y = find_root(y);
        if (x == y) return;

        if (ran[x] < ran[y]) {
            par[find_root(y)] += par[find_root(x)];
            par[x] = y;
        }
        else {
            par[find_root(x)] += par[find_root(y)];
            par[y] = x;
            if (ran[x] == ran[y]) ran[x]++;
        }
    }

    int size(int x) {
        return -par[find_root(x)];
    }

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

    int find_root(int x) {
        if (par[x] < 0) {
            return x;
        }
        else {
            return par[x] = find_root(par[x]);
        }
    }

private:
    std::vector<int> par, ran;
};


#line 5 "test/union_find.yosupo.unionfind.test.cpp"

int main() {
    int n, q; std::cin >> n >> q;
    UnionFind uf(n);
    for (int i = 0; i < q; i++) {
        int t, u, v; std::cin >> t >> u >> v;
        if (t) std::cout << uf.same(u, v) << std::endl;
        else uf.unite(u, v);
    }
    return 0;
}