verify/verify-yosupo-ds/yosupo-unionfind.test.cpp

• View this file on GitHub
• Last update: 2025-03-17 21:57:32+08:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• src/alfred/config/io-sync-off.hpp
• src/alfred/data_structure/dsu.hpp

Code

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

#include "../../src/alfred/config/io-sync-off.hpp"
#include "../../src/alfred/data_structure/dsu.hpp"
#include <iostream>

int main(int argc, char const *argv[]) {
    int n, q, opt, u, v;
    optimizeIO(), std::cin >> n >> q;

    DSU D(n);
    while (q--) {
        std::cin >> opt >> u >> v;
        if (opt == 0) {
            D.merge(u, v);
        } else {
            std::cout << D.same(u, v) << '\n';
        }
    }

    return 0;
}

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

#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>

inline void optimizeIO(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 1 "src/alfred/data_structure/dsu.hpp"



#line 6 "src/alfred/data_structure/dsu.hpp"

struct DSU {
    std::vector<int> fa, siz;
    DSU(int n) : fa(n + 1), siz(n + 1, 1) {
        std::iota(fa.begin(), fa.end(), 0);
    }
    inline int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    inline bool same(int x, int y) {
        return find(x) == find(y);
    }
    // true if x and y were not in the same set, false otherwise.
    inline bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return false;
        if (siz[fx] < siz[fy]) std::swap(fx, fy);
        fa[fy] = fx, siz[fx] += siz[fy], siz[fy] = 0;
        return true;
    }
    // x -> y, a.k.a let x be son of y (disable merge by rank).
    inline bool directed_merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return false;
        fa[fx] = fy, siz[fy] += siz[fx], siz[fx] = 0;
        return true;
    }
};


#line 6 "verify/verify-yosupo-ds/yosupo-unionfind.test.cpp"

int main(int argc, char const *argv[]) {
    int n, q, opt, u, v;
    optimizeIO(), std::cin >> n >> q;

    DSU D(n);
    while (q--) {
        std::cin >> opt >> u >> v;
        if (opt == 0) {
            D.merge(u, v);
        } else {
            std::cout << D.same(u, v) << '\n';
        }
    }

    return 0;
}

Back to top page