Q23: How do you implement Disjoint Set Union (DSU / Union-Find) with Path Compression and Union by Rank?

DSU manages partitioned disjoint sets across elements. Operations:

find(x): Returns root representative of x. Uses Path Compression (parent[x] = find(parent[x])) to flatten tree paths.
union(x, y): Connects sets containing x and y. Uses Union by Rank to attach smaller trees beneath taller tree roots. Amortized operational time: $O(alpha(n))$ (Nearly constant Inverse Ackermann function).

Union-Find with Path Compression & Rank

public class UnionFind {
    private final int[] parent;
    private final int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) parent[i] = i;
    }
    public int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]); // Path compression
    }
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else { parent[rootY] = rootX; rank[rootX]++; }
            return true;
        }
        return false; // Already in same set
    }
}

💡 Flattens set trees dynamically to execute union and find queries in near constant time.

Key Takeaways

Path Compression flattens parent pointers during find().
Union by Rank maintains balanced tree depth.
Amortized operational time complexity: $O(alpha(n))$.

Knowledge Check

What is the amortized time complexity per operation in a DSU implementation utilizing both Path Compression and Union by Rank?

Q23: How do you implement Disjoint Set Union (DSU / Union-Find) with Path Compression and Union by Rank?

STAY UPDATED WITH BYTES!