//
Implementation of Robert Tarjan's UnionFind algorithm. -Ken Perlin public class UnionFind { public UnionFind(int n) { // INIT EACH SUBSET INDEX TO ITSELF. I = new int[n]; // INIT EACH SUBSET SIZE TO ONE. S = new int[n]; for (int i = 0 ; i < n ; i++) { I[i] = i; S[i] = 1; } } public void union(int a, int b) { // IF NOT ALREADY IN SAME SUBSET, int i = find(a), j = find(b); // MERGE SMALL SUBSET INTO BIG ONE. if (i == j) return; int u = S[i] < S[j] ? i : j, v = i+j - u; I[u] = v; S[v] += S[u]; } public int find(int a) { // FIND ROOT INDEX r OF SUBSET; int r = a; // SET ALL INDICES OF SUBSET TO r. while (I[r] != r) r = I[r]; while (I[a] != r) { int t = I[a] ; I[a] = r; a = t; } return r; } private int I[], S[]; // INTERNAL STORAGE FOR SUBSET INDICES AND SIZES. }