test/DataStructure/UnionFind_unionfind.test.cpp

View this file on GitHub
Last update: 2023-11-12 00:32:16+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

UnionFind (src/DataStructure/UnionFind.hpp)

Code

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

#include <iostream>
#include "../../src/DataStructure/UnionFind.hpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    lib::UnionFind uf(N);
    for (int i = 0; i < Q; i++) {
        int t, u, v;
        std::cin >> t >> u >> v;
        if (t == 0) {
            uf.unite(u, v);
        } else {
            std::cout << uf.same(u, v) << '\n';
        }
    }
}

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

#include <iostream>
#line 2 "src/DataStructure/UnionFind.hpp"

#line 4 "src/DataStructure/UnionFind.hpp"
#include <vector>

namespace lib{
    class UnionFind {
    public:
        std::vector<int> par, siz;
        UnionFind(int n) : par(n, -1), siz(n, 1) {}

        // 経路圧縮あり
        int root(int x) {
            if (par[x] == -1) return x;
            return par[x] = root(par[x]);
        }

        // 経路圧縮なし
        /*int root(int x){
            if(par[x] == -1) return x;
            return root(par[x]);
        } */

        bool unite(int x, int y) {
            int rx = root(x), ry = root(y);
            if (rx == ry) return false;
            if (size(rx) < size(ry)) std::swap(rx, ry);

            par[ry] = rx;
            siz[rx] += siz[ry];
            return true;
        }

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

        int size(int x) { return siz[root(x)]; }
    };
}
#line 5 "test/DataStructure/UnionFind_unionfind.test.cpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    lib::UnionFind uf(N);
    for (int i = 0; i < Q; i++) {
        int t, u, v;
        std::cin >> t >> u >> v;
        if (t == 0) {
            uf.unite(u, v);
        } else {
            std::cout << uf.same(u, v) << '\n';
        }
    }
}