verifying_test/AOJ/DSL_1_A/union_find.test.cpp

• View this file on GitHub
• Last update: 2022-01-28 02:17:51+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp

Depends on

• Union-Find (structure/union_find.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp"

#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; scanf("%d", &t);
        int x, y; scanf("%d%d", &x, &y);
        if(t == 0) {
            uf.unite(x, y);
        }
        if(t == 1) {
            printf("%d\n", uf.same(x, y) ? 1 : 0);
        }
    }
}

#line 1 "verifying_test/AOJ/DSL_1_A/union_find.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp"

#include <cstdio>
using namespace std;

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

/**
 * @brief Union-Find
 * @docs docs/structure/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) {}
    void reset() {
        size_ = n;
        fill(uf.begin(), uf.end(), -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/AOJ/DSL_1_A/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; scanf("%d", &t);
        int x, y; scanf("%d%d", &x, &y);
        if(t == 0) {
            uf.unite(x, y);
        }
        if(t == 1) {
            printf("%d\n", uf.same(x, y) ? 1 : 0);
        }
    }
}

Back to top page