Ｕｎｉｏｎ−Ｆｉｎｄ

// int nc    現在の総グループ数
// init      初期化する n は要素数
// find      要素の親を探す
// union_    要素aと要素bを結合(union_ にはアンダーバーがついています。)
// check     要素aと要素bが結合されていれば 1 そうでなければ 0 を返す
// get_size  要素aの含まれるグループの要素数

// nc のみ変数でアクセス nc に書き込まないこと
// その他は関数を用いること

vector<int> uf, usz;
int nc;

void init(int n){
  vector<int> uf_(n);
  vector<int> usz_(n, 1);
  uf = uf_;
  usz = usz_;
  nc = n;

  for(int i = 0; i < uf.size(); i++){
    uf[i] = i;
  }
}

int find(int a){
  return (uf[a] == a) ? a : uf[a] = find(uf[a]);
}

void union_(int a, int b){
  a = find(a);
  b = find(b);

  if(a != b){
    if(usz[a] >= usz[b]){
      swap(a, b);
    }
    uf[a] = b;
    usz[b] += usz[a];
    nc--;
  }
}

int check(int a, int b){
  return (find(a) == find(b)) ? 1 : 0;
}

int get_size(int a){
  return usz[find(a)];
}