Union-Find Warm-Up
Disjoint Set Union with path compression and union by rank. Drills cover find, union, connected-component counts, and Kruskal usage.
Question Bank
Medium
JavaScript
4 questions
union-find
union-by-rank
data-structures
quiz
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.class DSU {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
// TODO
}
union(a, b) {
// TODO: return true if a merge happened, false if already same set
}
}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.// Sequence: union(0, 1), union(2, 3), union(0, 2), union(4, 5)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.function countComponents(n, edges) {
// TODO
}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?