Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A Disjoint Set Union (DSU, also called Union-Find) maintains a partition of a set of elements into disjoint subsets
A Disjoint Set Union (DSU, also called Union-Find) maintains a partition of a set of elements into disjoint subsets.
It supports two operations in near-constant amortized time: `find(x)` (which set does x belong to?) and `union(a, b)` (merge the sets of a and b).
Two optimizations — union by rank and path compression — combine to give O(α(n)) per operation, where α is the inverse Ackermann function.
How It Works
Each set is represented by a rooted tree: `parents[i]` points to the parent of i, and the root of a tree is the set representative.
`find(x)` walks up the parent chain to the root, compressing the path as it goes (each visited node points directly to the root).
`union(a, b)` links the root of the smaller tree (lower rank) under the root of the larger tree, keeping trees shallow.
Repeated finds get faster as paths compress.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| find(x) | O(α(n)) ≈ O(1) | O(1) |
| union(a, b) | O(α(n)) ≈ O(1) | O(1) |
| Path compression | Amortized, accelerates all future finds | — |
| Union by rank | Keeps trees at height O(log n) | — |
| Total storage | O(n) | O(n) |
Best Use Cases
- Kruskal's algorithm — cycle detection while building an MST
- Dynamic connectivity — "are these two nodes connected?" queries over time
- Detecting cycles in undirected graphs
- Image segmentation (pixel region merging)
- Network / cluster equivalence grouping
Worked Example
Union pairs (0,1), (2,3), (4,5), (1,3), (5,2), (0,4) on 6 nodes
Input: nodes 0–5; union in order: [0,1], [2,3], [4,5], [1,3], [5,2], [0,4]- 1 Union(0,1): 0 and 1 join a set. Union(2,3): 2 and 3 join another.
- 2 Union(4,5): 4 and 5 join a third set — three disjoint groups so far.
- 3 Union(1,3): merges {0,1} and {2,3} into one component of four nodes.
- 4 Union(5,2): merges {4,5} into the big component — now five nodes share a root.
- 5 Union(0,4): both are already in the same component; find(0) == find(4), so this is a no-op that still illustrates cycle detection.
- 6 Union by rank keeps trees shallow; path compression flattens them further.
Pseudocode
function find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # compress
return parent[x] function union(a, b):
ra = find(a); rb = find(b)
if ra == rb: return
if rank[ra] < rank[rb]:
parent[ra] = rb
elif rank[ra] > rank[rb]:
parent[rb] = ra
else:
parent[rb] = ra; rank[ra]++ Union Sequence
Watch the disjoint sets merge with union by rank and find with path compression.