cpp_library

This documentation is automatically generated by online-judge-tools/verification-helper

This project is maintained by tsutaj

:heavy_check_mark: verifying_test/yosupo/data_structure/unionfind/union_find.test.cpp

Back to top page

Depends on

Code

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

#include <cstdio>
using namespace std;

#define call_from_test
#include "../../../../structure/union_find.cpp"
#undef call_from_test

int main() {
    int N, Q; scanf("%d%d", &N, &Q);
    UnionFind uf(N);
    while(Q--) {
        int t, u, v; scanf("%d%d%d", &t, &u, &v);
        if(t == 0) uf.unite(u, v);
        else printf("%d\n", uf.same(u, v) ? 1 : 0);
    }
    return 0;
}

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

#include <cstdio>
using namespace std;

#define call_from_test
#line 2 "structure/union_find.cpp"

/**
 * @brief Union-Find
 * @docs ./docs/union_find.md
 */

#include <algorithm>
#include <vector>

struct UnionFind {
private:
    const int n;
    int size_;
    vector<int> uf;
public:
    // 初期化 UnionFind uni(n) のように宣言すれば良い
    UnionFind(int _n) : n(_n), size_(_n), uf(_n, -1) {}
    // find (木の根を求める)
    int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
    // x と y が同じ集合に属するかどうか
    bool same(int x, int y) {return find(x) == find(y);}
    // x が属する集合の要素数
    int size(int x) {return -uf[find(x)];}
    // 集合はいくつあるか
    int size()      {return size_;}
    // x と y の属する集合を併合
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return false;
        size_--;
        if(-uf[x] < -uf[y]) swap(x, y);
        uf[x] += uf[y]; uf[y] = x;
        return true;
    }
};
#line 8 "verifying_test/yosupo/data_structure/unionfind/union_find.test.cpp"
#undef call_from_test

int main() {
    int N, Q; scanf("%d%d", &N, &Q);
    UnionFind uf(N);
    while(Q--) {
        int t, u, v; scanf("%d%d%d", &t, &u, &v);
        if(t == 0) uf.unite(u, v);
        else printf("%d\n", uf.same(u, v) ? 1 : 0);
    }
    return 0;
}

Back to top page