1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | class UnionFind { int count; int[] parent; int[] size; public UnionFind(int n) { parent = new int[n]; size = new int[n]; count = n; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } public find(int a) { int root = a; while (parent[root] != root) root = parent[root]; compress(a, root); return root; } public void compress(int a, int root) { while (a != root) { int next = parent[a]; parent[a] = root; a = next; } } public void union(int a, int b) { if (find(a) == find(b)) return; int ap = parent[a]; int bp = parent[b]; if (size[ap] <= size[bp]) { parent[ap] = bp; size[bp] += size[ap]; compress(a, bp); } else { parent[bp] = ap; size[ap] += size[bp]; compress(b, ap); } count--; } } |
Categories