datastructures12UnionFind

1package pkg3datastructures;2 3/*4 * datastructures12UnionFind.java  (Disjoint Set Union, DSU)5 * -----------------------------------------6 * Tracks a partition of elements into disjoint sets with near-constant-time7 * union and find, using PATH COMPRESSION + UNION BY RANK.8 *9 * COMPLEXITY: ~O(alpha(n)) per op (inverse Ackermann, effectively constant).10 * WHEN TO USE: connectivity, Kruskal's MST, cycle detection, grouping.11 */12public class datastructures12UnionFind {13 14    private final int[] parent, rank;15    private int components;16 17    datastructures12UnionFind(int n) {18        parent = new int[n];19        rank = new int[n];20        components = n;21        for (int i = 0; i < n; i++) parent[i] = i;   // each element is its own set22    }23 24    int find(int x) {25        if (parent[x] != x) parent[x] = find(parent[x]);  // path compression26        return parent[x];27    }28 29    boolean union(int a, int b) {30        int ra = find(a), rb = find(b);31        if (ra == rb) return false;                        // already connected32        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }33        parent[rb] = ra;                                   // attach smaller under larger34        if (rank[ra] == rank[rb]) rank[ra]++;35        components--;36        return true;37    }38 39    boolean connected(int a, int b) { return find(a) == find(b); }40    int components() { return components; }41 42    public static void main(String[] args) {43        datastructures12UnionFind uf = new datastructures12UnionFind(6);   // elements 0..544        uf.union(0, 1);45        uf.union(1, 2);46        uf.union(3, 4);47        System.out.println("connected(0,2): " + uf.connected(0, 2));   // true48        System.out.println("connected(0,3): " + uf.connected(0, 3));   // false49        System.out.println("components: " + uf.components());          // {0,1,2} {3,4} {5} -> 350        uf.union(2, 4);51        System.out.println("after union(2,4) connected(0,3): " + uf.connected(0, 3));52        System.out.println("components: " + uf.components());53    }54}