Union-Find Tree

#include<vector>

struct Unionfind {
  vector<int> par, rank, size;

  Unionfind(int n) : par(n), rank(n), size(n){
    for(int i=0;i<n;i++){
      par[i] = i;
      rank[i] = 0;
      size[i] = 1;
    }
  }

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

  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]){
      par[x] = par[y];
      size[y] += size[x];
    }else{
      par[y] = par[x];
      size[x] += size[y];
      if(par[x] == par[y]) rank[x]++;
    }
  }

  int get_size(int x) {
    return size[find(x)];
  }

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