program_contest_library

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

View the Project on GitHub ferin-15/program_contest_library

:heavy_check_mark: test/yosupo-unionfind.test.cpp

Back to top page

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include "../memo/macro.hpp"
#include "../data_structure/unionfind.cpp"

int main() {
    ll n, q;
    cin >> n >> q;
    UnionFind uf(n);
    REP(i, q) {
        ll t, u, v;
        cin >> t >> u >> v;
        if(t == 0) uf.unite(u, v);
        else cout << uf.same(u, v) << "\n";
    }
    cout << flush;

    return 0;
}

#line 1 "test/yosupo-unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#line 1 "memo/macro.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
const ll INF = 1LL<<60;
#line 1 "data_structure/unionfind.cpp"
// BEGIN CUT
struct UnionFind {
    vector<ll> par, s;
    UnionFind(ll n) : par(n), s(n, 1) { iota(ALL(par), 0); }
    ll find(ll x) {
        if(par[x] == x) return x;
        return par[x] = find(par[x]);
    }
    void unite(ll x, ll y) {
        x = find(x), y = find(y);
        if(x == y) return;
        if(s[x] < s[y]) par[x] = y, s[y] += s[x];
        else par[y] = x, s[x] += s[y];
    }
    bool same(int x, int y) { return find(x) == find(y); }
    ll size(int x) { return s[find(x)]; }
};
// END CUT
#line 4 "test/yosupo-unionfind.test.cpp"

int main() {
    ll n, q;
    cin >> n >> q;
    UnionFind uf(n);
    REP(i, q) {
        ll t, u, v;
        cin >> t >> u >> v;
        if(t == 0) uf.unite(u, v);
        else cout << uf.same(u, v) << "\n";
    }
    cout << flush;

    return 0;
}

Back to top page