Disjoint Set Union

struct DSU
{
  vector<int> p, s;
  vector<vector<int> > G;
  void init(int n){
    p.resize(n + 1);
    G.resize(n + 1);
    s.resize(n + 1);
    for(int i = 1; i <= n; ++i)
      p[i] = i, s[i] = 1;
      G[i].pb(i);
  }  
  int get(int v){
    return v == p[v] ? v : p[v] = get(p[v]);
  }
  bool merge(int x, int y){
    x = get(x), y = get(y);
    if(x != y){
      if(s[x] < s[y]) swap(x, y);
      p[y] = x;
      s[x] += s[y];
      while(!G[y].empty()){
        G[x].push_back(G[y].back());
        G[y].pop_back();
      }
      return true;
    }
    return false;
  }
};