verify/yosupo_library_checker/data_structure/Union_Find.test.cpp

• View this file on GitHub
• Last update: 2025-08-16 18:41:41+09:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• Union_Find/Union_Find.hpp

Code

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

#include<bits/stdc++.h>

using namespace std;

#include"../../../Union_Find/Union_Find.hpp"

int main() {
    int N, Q; cin >> N >> Q;
    Union_Find U(N);

    for (int q = 1; q <= Q; q++){
        int t, u, v; scanf("%d%d%d", &t, &u, &v);
        if (t == 0) { U.unite(u, v); }
        else if (t == 1) { cout << U.same(u, v) << "\n"; }
    }
}

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

#include<bits/stdc++.h>

using namespace std;

#line 2 "Union_Find/Union_Find.hpp"

class Union_Find{
    private:
    int N;
    vector<int> data;
    int group_number;

    public:
    Union_Find(int N) : N(N), data(N, -1), group_number(N) {}

    // x が属する族の代表元を求める.
    int find(int x) { return data[x] < 0 ? x: data[x] = find(data[x]); }

    // x と y を結合する.
    // 返り値: 元々非連結ならば true, 連結ならば false
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) { return false; }

        if (data[x] > data[y]) { swap(x, y); }

        data[x] += data[y];
        data[y] = x;

        group_number--;

        return true;
    }

    // x が属する族における位数を求める.
    int size(int x) { return -data[find(x)]; }

    // x, y は同じ連結成分にある?
    int same(int x, int y) { return find(x) == find(y); }
};
#line 8 "verify/yosupo_library_checker/data_structure/Union_Find.test.cpp"

int main() {
    int N, Q; cin >> N >> Q;
    Union_Find U(N);

    for (int q = 1; q <= Q; q++){
        int t, u, v; scanf("%d%d%d", &t, &u, &v);
        if (t == 0) { U.unite(u, v); }
        else if (t == 1) { cout << U.same(u, v) << "\n"; }
    }
}

Back to top page