UnionFind - nise-nabe/topcoder GitHub Wiki

  static class UnionFind {
    int[] par;
    int[] rank;

    public UnionFind(int n) {
      par = new int[n];
      rank = new int[n];
      for (int i = 0; i < n; ++i) {
        par[i] = i;
        rank[i] = 0;
      }
    }

    int find(int x) {
      return (par[x] == x) ? x : (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] = y;
      } else {
        par[y] = x;
        if (rank[x] == rank[y])
          ++rank[x];
      }
    }

    boolean isSame(int x, int y) {
      return find(x) == find(y);
    }
    
    int size() {
      java.util.Set<Integer> set = new java.util.HashSet<Integer>();
      for(int p : par) {
        set.add(find(p));
      }
      return set.size();
    }
  }