test/data_structure/unionfind.0.test.cpp

View this file on GitHub
Last update: 2024-06-23 11:19:57+08:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

disjoint_set.hpp

Code

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

#include "disjoint_set.hpp"
#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    DisjointSet s(n);
    while (q--) {
        int t, u, v;
        std::cin >> t >> u >> v;
        if (t == 0) {
            s.unite(u, v);
        } else {
            std::cout << s.is_same(u, v) << '\n';
        }
    }
    return 0;
}

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

#line 2 "disjoint_set.hpp"

#include <numeric>
#include <vector>

class DisjointSet {
    mutable std::vector<int> P;
    std::vector<int> S;

public:
    DisjointSet() = default;
    explicit DisjointSet(int N) : P(N), S(N) { std::iota(P.begin(), P.end(), 0); }
    void make_set(int N) {
        P.resize(N);
        S.assign(N, 1);
        std::iota(P.begin(), P.end(), 0);
    }
    int root(int u) const {
        // path halving
        while (P[u] != P[P[u]]) u = P[u] = P[P[u]];
        return P[u];
    }
    bool is_same(int u, int v) const { return root(u) == root(v); }
    int unite(int u, int v) {
        u = root(u), v = root(v);
        if (u == v) return u;
        if (S[u] < S[v]) return S[v] += S[u], P[u] = v;
        return S[u] += S[v], P[v] = u;
    }
    int component_size(int u) const { return S[root(u)]; }
};
#line 4 "test/data_structure/unionfind.0.test.cpp"
#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    DisjointSet s(n);
    while (q--) {
        int t, u, v;
        std::cin >> t >> u >> v;
        if (t == 0) {
            s.unite(u, v);
        } else {
            std::cout << s.is_same(u, v) << '\n';
        }
    }
    return 0;
}