test/library_checker/data_structure/unionfind_1.test.cpp

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• lib/data_structure/dynamic_union_find.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/data_structure/dynamic_union_find.hpp"

int main(){
    int n, q; cin >> n >> q;
    DynamicUnionFind<int> tree;
    while(q--){
        int t, u, v; cin >> t >> u >> v;
        if(t == 0){
            tree.unite(u, v);
        }else{
            if(tree.same(u, v)){
                cout << 1 << "\n";
            }else{
                cout << 0 << "\n";
            }
        }
    }
}

#line 1 "test/library_checker/data_structure/unionfind_1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/data_structure/dynamic_union_find.hpp"

/*
    DynamicUnionFind(n) : Union-Find 木をサイズnで構築
    計算量 : O(a(n)) -> アッカーマンの逆関数
    root(x) : 集合 x の根を取得します。
    unite(x, y) : 集合 x と y を併合します。
    same(x, y) : 集合 x と 集合 y が等しいかどうかを判定します。
    size(x) : x を含む集合の大きさを取得します。
*/

template <typename T>
struct DynamicUnionFind{
    unordered_map<T, T> par, siz;

    DynamicUnionFind(){
    }

    void init(const T &x){
        par[x] = x;
        siz[x] = 1;
    }

    T root(const T &x){
        if(par.find(x) == par.end()){
            init(x);
        }
        if(par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(const T &x, const T &y){
        if(par.find(x) == par.end()){
            init(x);
        }
        if(par.find(y) == par.end()){
            init(y);
        }
        int rx = root(x);
        int ry = root(y);
        if(size(rx) < size(ry)) swap(rx, ry);
        par[rx] = ry;
        siz[ry] += siz[rx];
    }

    bool same(const T &x, const T &y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    T size(const T &x){
        if(par.find(x) == par.end()){
            init(x);
        }
        return siz[root(x)];
    }
};
#line 6 "test/library_checker/data_structure/unionfind_1.test.cpp"

int main(){
    int n, q; cin >> n >> q;
    DynamicUnionFind<int> tree;
    while(q--){
        int t, u, v; cin >> t >> u >> v;
        if(t == 0){
            tree.unite(u, v);
        }else{
            if(tree.same(u, v)){
                cout << 1 << "\n";
            }else{
                cout << 0 << "\n";
            }
        }
    }
}

Back to top page