Система непересекающихся множеств

class dsu {
  int p[]; // parents
  int r[]; // rangs
  int N; // number of elements

  dsu(int N) {
    this.N = N;
    p = new int[N];
    r = new int[N];
    for (int i = 0; i < N; i++) {
      p[i] = i;
      r[i] = 1;
    }
  }

  int get(int x) {
    return (x == p[x] ? x : p[x] = get(p[x]));
  }

  void union(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) return;
    if (r[x] == r[y]) r[x]++;
    if (r[x] < r[y]) 
      p[x] = p[y]; else
      p[y] = p[x];
  }
}