test/yosupo/ds/unionfind.test.cpp

• View this file on GitHub
• Last update: 2025-09-20 17:47:50+07:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• Disjoint Set Union (graph/dsu.hpp)

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "graph/dsu.hpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    DSU dsu(n);
    while (q--) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) {
            dsu.merge(u, v);
        } else {
            cout << dsu.same(u, v) << "\n";
        }
    }
}

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

#include <bits/stdc++.h>
using namespace std;

#line 2 "graph/dsu.hpp"

struct DSU {
    vector<int> data;
    DSU() : DSU(0) {}
    DSU(int n) : data(n, -1) {}

    void reset(int n) {
        if (data.size() < n) data.resize(n);
        fill_n(begin(data), n, -1);
    }
    int size(int x) { return -data[find(x)]; }
    int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        return merge(x, y, [](auto...) {});
    }
    template<class F> bool merge(int x, int y, F &&f) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += exchange(data[y], x);
        f(x, y);
        return true;
    }
};
#line 7 "test/yosupo/ds/unionfind.test.cpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    DSU dsu(n);
    while (q--) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) {
            dsu.merge(u, v);
        } else {
            cout << dsu.same(u, v) << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	42 ms	4 MB
g++	max_random_01	AC	44 ms	4 MB
g++	max_random_02	AC	40 ms	4 MB
g++	path_00	AC	37 ms	4 MB
g++	path_01	AC	37 ms	4 MB
g++	path_02	AC	36 ms	4 MB
g++	path_03	AC	36 ms	4 MB
g++	random_00	AC	33 ms	4 MB
g++	random_01	AC	33 ms	4 MB
g++	random_02	AC	27 ms	4 MB
g++	random_03	AC	10 ms	4 MB
g++	random_04	AC	22 ms	4 MB
g++	random_05	AC	30 ms	4 MB
g++	random_06	AC	26 ms	4 MB
g++	random_07	AC	7 ms	4 MB
g++	random_08	AC	13 ms	4 MB
g++	random_09	AC	41 ms	4 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_random_00	AC	43 ms	4 MB
clang++	max_random_01	AC	45 ms	4 MB
clang++	max_random_02	AC	40 ms	4 MB
clang++	path_00	AC	37 ms	4 MB
clang++	path_01	AC	38 ms	4 MB
clang++	path_02	AC	37 ms	4 MB
clang++	path_03	AC	36 ms	4 MB
clang++	random_00	AC	33 ms	4 MB
clang++	random_01	AC	33 ms	4 MB
clang++	random_02	AC	27 ms	4 MB
clang++	random_03	AC	10 ms	4 MB
clang++	random_04	AC	22 ms	4 MB
clang++	random_05	AC	30 ms	4 MB
clang++	random_06	AC	26 ms	4 MB
clang++	random_07	AC	8 ms	4 MB
clang++	random_08	AC	13 ms	4 MB
clang++	random_09	AC	41 ms	4 MB

Back to top page