test/unionfind.test.cpp

View this file on GitHub
Last update: 2021-05-27 03:43:35+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

datastructure/UnionFind.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include <vector>
#include <cassert>
#include <iostream>
#include "../datastructure/UnionFind.hpp"

int main(){
  int N, Q; std::cin >> N >> Q;
  UnionFind uf(N);
  while(Q--){
    int t, u, v;
    std::cin >> t >> u >> v;
    if(t == 0){
      uf.merge(u, v);
    }else{
      if(uf.issame(u,v)) std::cout << 1 << '\n';
      else std::cout << 0 << '\n';
    }
  }
}

#line 1 "test/unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include <vector>
#include <cassert>
#include <iostream>
#line 4 "datastructure/UnionFind.hpp"
struct UnionFind{
  std::vector<int> par;
  std::vector<int> siz;

  UnionFind(int sz_): par(sz_), siz(sz_) {
    for(int i=0; i<sz_; ++i) par[i] = i, siz[i] = 1;
  }

  void init(int sz_){
    par.resize(sz_);
    siz.resize(sz_);
    for(int i=0; i<sz_; ++i) par[i] = i, siz[i] = 1;
  }

  int root(int x){
    if(x == par[x]) return x;
    return par[x] = root(par[x]);
  }

  bool merge(int x, int y){
    x = root(x), y = root(y);
    if(x == y) return false;
    if(siz[x] < siz[y]) std::swap(x, y);
    siz[x] += siz[y];
    par[y] = x;
    return true;
  }

  bool issame(int x, int y){
    return root(x) == root(y);
  }

  int size(int x){
    return siz[root(x)];
  }
};
#line 6 "test/unionfind.test.cpp"

int main(){
  int N, Q; std::cin >> N >> Q;
  UnionFind uf(N);
  while(Q--){
    int t, u, v;
    std::cin >> t >> u >> v;
    if(t == 0){
      uf.merge(u, v);
    }else{
      if(uf.issame(u,v)) std::cout << 1 << '\n';
      else std::cout << 0 << '\n';
    }
  }
}