SpecializedSpecialized Structures

Union-Find (Disjoint Set Union)

Tracks a partition of elements into disjoint sets with near-constant-time find and union, using path compression and union by rank.

Learn Union-Find (Disjoint Set Union) →
0r01r02r03r04r05r06r07r0
a
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
rank
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
parent[i] shown below — i is a root when parent[i] = i · n = 8
Sets
rootrankmembers
000
101
202
303
404
505
606
707
1/638 elements, each its own set: parent[i] = i and rank 0. The parent array encodes a forest; the root of a tree names its set.
Element being processedOn the path to the rootSet representativeRelinked (compression / union)
PseudocodeLearn Union-Find (Disjoint Set Union) →
1find(x): while parent[x] != x: x = parent[x]   # walk to the root
2  path compression: point every node on the path directly at the root
3union(a, b): ra = find(a); rb = find(b)
4  if ra == rb: already same set
5  attach the root with smaller rank under the other (union by rank)
6  if ranks are equal: rank[new root] += 1
Variables
n8
sets8
Complexity
access —
search O(α(n))
insert O(1)
delete —
Speed