/** * Created with IntelliJ IDEA. * User: Andrey Kudryavtsev * Date: 07.11.13 * Time: 22:11 */ public class WeightedQuickUF { private int[] id; // id[i] = parent of i private int[] sz; // sz[i] = number of objects in subtree rooted at i private int count; // number of components /** * Create an empty union find data structure with N isolated sets. * * @param N Num of sets */ public WeightedQuickUF(int N) { count = N; id = new int[N]; sz = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; sz[i] = 1; } } /** * Return the number of disjoint sets. * * @return the number of disjoint sets */ public int count() { return count; } /** * Return component identifier for component containing p * * @param p * @return component identifier for component containing p */ public int find(int p) { while (p != id[p]) p = id[p]; return p; } /** * Are objects p and q in the same set? * * @param p object1 * @param q object2 * @return Are objects p and q in the same set */ public boolean isConnected(int p, int q) { return find(p) == find(q); } /** * Replace sets containing p and q with their union. * * @param p object1 * @param q object2 */ public void union(int p, int q) { int i = find(p); int j = find(q); if (i == j) return; // make smaller root point to larger one if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; } count--; } }