test/union_find.test.cpp

View this file on GitHub
Last update: 2020-11-27 17:14:27+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

Code

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

#include "src/template.hpp"
#include "src/union_find.hpp"

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) << el;
    }
  }
}

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

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0; i < (ll)n; i++)
#define rep3(i, l, r) for(ll i = l; i < (ll)r; i++)
#define per(i, n) for(ll i = (ll)n-1; i >= 0; i--)
#define per3(i, l, r) for(ll i = (ll)r-1; i >= (ll)l; i--)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
template<class T, class U> inline void cmax(T &a, U b) { if (a < b) a = b; }
template<class T, class U> inline void cmin(T &a, U b) { if (a > b) a = b; }
constexpr char el = '\n';
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) os << v[i] << (i+1 != (ll)v.size() ? " " : ""); return os; }
template<class T> istream &operator>>(istream &is, vector<T> &v) { for(T &i : v) is >> i; return is; }
struct IoSetup {
  IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); }
} io_setup;
#line 3 "src/union_find.hpp"

struct UnionFind {
  struct Node {
    ll parent;
    ll size;
  };
  vector<Node> data;
  ll num;

  UnionFind(ll size) : data(size) {
    rep(i, size) {
      data[i].parent = i;
      data[i].size = 1;
    }
    num = size;
  }

  ll find(ll x) {
    while (data[x].parent != x) {
      ll p = data[x].parent;
      data[x].parent = data[p].parent;
      x = p;
    }
    return x;
  }

  void unite(ll x, ll y) {
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (data[x].size < data[y].size) swap(x, y);
    data[y].parent = x;
    data[x].size += data[y].size;
    num--;
  }

  bool same(ll x, ll y) {
    return find(x) == find(y);
  }

  ll count() const {
    return num;
  }
};
#line 5 "test/union_find.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) << el;
    }
  }
}