Union-Find (DSU)
MediumDisjoint sets · find + union
Group items by linking them under a shared leader; two items are connected if they share a leader.
The idea
Disjoint-Set Union tracks which elements belong to the same group. 'find' returns a group's representative (with path compression), 'union' merges two groups by rank — near O(1) each.
Step 1 of 10. Union-Find keeps disjoint groups. union(a,b) links one root under the other.
1/10
Optimal
timeO(α(n))spaceO(n)
Almost constant per op.
1function find(x) {2 while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3 return x;4}5function union(a, b) {6 a = find(a); b = find(b);7 if (a === b) return false;8 if (rank[a] < rank[b]) [a, b] = [b, a];9 p[b] = a; if (rank[a] === rank[b]) rank[a]++;10 return true;11}Input
- nodes
- 5, 0 edges
Memory
- groups
- —
Output
- groups
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- union(1,2), union(3,4), find(1) == find(2)
- Output:
- true
- Explanation:
- 1 and 2 now share a root, so they are in one component. find(1) == find(3) is still false.
Example 2
- Input:
- union(2,3) after the above, then count roots
- Output:
- 1 component
- Explanation:
- Joining the two groups makes every node share a root. Union by rank keeps the tree shallow, and path compression flattens it as you query.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.