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

• View this file on GitHub
• Last update: 2025-03-29 17:57:48+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

// competitive-verifier: 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"
// competitive-verifier: 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;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	43 ms	4 MB
g++	max_random_01	AC	43 ms	4 MB
g++	max_random_02	AC	39 ms	4 MB
g++	path_00	AC	38 ms	5 MB
g++	path_01	AC	37 ms	5 MB
g++	path_02	AC	39 ms	5 MB
g++	path_03	AC	35 ms	5 MB
g++	random_00	AC	33 ms	4 MB
g++	random_01	AC	33 ms	5 MB
g++	random_02	AC	26 ms	4 MB
g++	random_03	AC	10 ms	5 MB
g++	random_04	AC	21 ms	4 MB
g++	random_05	AC	29 ms	4 MB
g++	random_06	AC	25 ms	5 MB
g++	random_07	AC	7 ms	4 MB
g++	random_08	AC	12 ms	4 MB
g++	random_09	AC	42 ms	4 MB

Back to top page