Verify/union_find.test.cpp

• View this file on GitHub
• Last update: 2020-10-29 02:20:23+09:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• DataStructure/union_find.hpp

Code

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

#include "../DataStructure/union_find.hpp"

#include <iostream>

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

    int n, q;
    std::cin >> n >> q;

    UnionFind uf(n);
    while (q--) {
        int t, u, v;
        std::cin >> t >> u >> v;

        if (t == 0) {
            uf.unite(u, v);
        } else {
            std::cout << uf.same(u, v) << "\n";
        }
    }

    return 0;
}

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

#line 2 "DataStructure/union_find.hpp"

#include <vector>

struct UnionFind {
    std::vector<int> par;
    int gnum;

    explicit UnionFind(int n) : par(n, -1), gnum(n) {}

    int find(int v) {
        return (par[v] < 0) ? v : (par[v] = find(par[v]));
    }

    void unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (par[u] > par[v]) std::swap(u, v);
        par[u] += par[v];
        par[v] = u;
        --gnum;
    }

    bool same(int u, int v) { return find(u) == find(v); }
    bool ispar(int v) { return par[v] < 0; }
    int size(int v) { return -par[find(v)]; }
};
#line 4 "Verify/union_find.test.cpp"

#include <iostream>

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

    int n, q;
    std::cin >> n >> q;

    UnionFind uf(n);
    while (q--) {
        int t, u, v;
        std::cin >> t >> u >> v;

        if (t == 0) {
            uf.unite(u, v);
        } else {
            std::cout << uf.same(u, v) << "\n";
        }
    }

    return 0;
}

Back to top page