test/DSL1A.test.cpp

Back to top page

• category: test
• View this file on GitHub
  • Last commit date: 2020-03-01 12:39:31+09:00
• see: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_A

Depends on

• data_structure/unionfind.cpp
• memo/macro.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_A"
#include "../memo/macro.hpp"
#include "../data_structure/unionfind.cpp"

signed main(void) {
    ll n, q;
    cin >> n >> q;
    UnionFind uf(n);
    while(q--) {
        ll type;
        cin >> type;
        if(type == 0) {
            ll x, y;
            cin >> x >> y;
            uf.unite(x, y);
        } else {
            ll x, y;
            cin >> x >> y;
            cout << uf.same(x, y) << endl;
        }
    }

    return 0;
}

#line 1 "test/DSL1A.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_A"
#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/DSL1A.test.cpp"

signed main(void) {
    ll n, q;
    cin >> n >> q;
    UnionFind uf(n);
    while(q--) {
        ll type;
        cin >> type;
        if(type == 0) {
            ll x, y;
            cin >> x >> y;
            uf.unite(x, y);
        } else {
            ll x, y;
            cin >> x >> y;
            cout << uf.same(x, y) << endl;
        }
    }

    return 0;
}

Back to top page