Question Bank
Union-Find Warm-Up
Difficulty: Medium
Disjoint Set Union with path compression and union by rank. Drills cover find, union, connected-component counts, and Kruskal usage.
Union-Find Warm-Up
Disjoint Set Union with path compression and union by rank. Drills cover find, union, connected-component counts, and Kruskal usage.
1,097 views
13
Implement find with path compression and union by rank for a DSU over n elements.
Examples
Example 1:
Input: new DSU(4); union(0, 1); union(0, 2); find(2); then union(2, 1)
Output: find(2) returns 0; the final union returns false
Explanation: After the first two unions, {0, 1, 2} share root 0. find(2) compresses the path to 0. The fourth call sees that roots already match (0 == 0) and returns false. Amortized inverse-Ackermann per op.Starting with 6 disjoint nodes labeled 0..5, apply the union sequence below using union by rank. List the parent array after each union.
Examples
Example 1:
Input: 6 nodes labeled 0..5; apply union(0, 1), union(2, 3), union(0, 2), union(4, 5) using union-by-rank
Output: parent = [0, 0, 0, 2, 4, 4]
Explanation: After union(0, 1) and union(2, 3): parent = [0, 0, 2, 2, 4, 5]. After union(0, 2) (both rank 1), attach 2 under 0, parent = [0, 0, 0, 2, 4, 5]. After union(4, 5): parent = [0, 0, 0, 2, 4, 4]. Note parent[3] is still 2; only a future find would compress it.Given n nodes and an edge list of an undirected graph, count the number of connected components using DSU.
Examples
Example 1:
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2
Explanation: Start with 5 components. union(0, 1) merges -> 4. union(1, 2) merges -> 3. union(3, 4) merges -> 2. The function returns the count after processing all edges.Why does using only path compression (no rank / size heuristic) still give O(log n) amortized per operation, and why is the rank heuristic still recommended?