Disjoint Set (Union-Find) Data Structure

Maintain a partition of n elements into disjoint sets and support three operations — MakeSet, Find, and Union — in nearly O(1) amortized time using union by rank and path compression. The backbone of Kruskal's MST and many connectivity problems.

The problem it solves

Suppose you have n elements and a stream of operations of two kinds:

Union(u, v) — merge the set containing u with the set containing v.
Find(u) — return a representative of the set containing u. Two elements are in the same set iff Find(u) == Find(v).

This is the dynamic connectivity problem. It shows up everywhere — Kruskal's MST ("would adding this edge create a cycle?"), connected-component tracking in offline graphs, image segmentation, the classic 'percolation' problem, network connectivity, equivalence-class building, and many more.

A naive approach (one boolean matrix or one BFS per query) is far too slow. The disjoint-set forest answers both operations in essentially constant amortized time with two clever heuristics.

The structure — a forest of rooted trees

Each set is stored as a rooted tree. Every element holds one pointer: parent[u]. The root points to itself.

To find the representative of u, walk parent pointers until you hit a root. The root is the representative.

Example

Sets {1, 4, 5} and {2, 3, 6, 7}:

5 3

│ / \

4 2 6

│ │

1 7

parent: 1→4, 4→5, 5→5, 2→3, 3→3, 6→3, 7→6

Without further care, these trees can become long chains, making Find slow. Two optimizations keep them shallow:

1. Union by rank — when merging two trees, attach the shorter one under the taller one. rank[u] is an upper bound on the height of u's subtree.

2. Path compression — during Find, re-point every visited node directly to the root. Subsequent Finds along the same path become O(1).

With both, every operation runs in O(α(n)) amortized time, where α is the inverse Ackermann function — for any conceivable input, α(n) ≤ 4. So effectively constant.

The three operations

MakeSet(u) — create a singleton set: parent[u] = u, rank[u] = 0.

Find(u) — climb to the root; on the way back, compress the path:

Example

Find(u):

if parent[u] != u:

parent[u] = Find(parent[u]) // compress

return parent[u]

Union(u, v) — find both roots; if they differ, link the lower-rank tree under the higher-rank one:

Example

Union(u, v):

ru = Find(u); rv = Find(v)

if ru == rv: return // already in the same set

if rank[ru] < rank[rv]: parent[ru] = rv

else if rank[ru] > rank[rv]: parent[rv] = ru

else: parent[rv] = ru; rank[ru] += 1

Step-by-step visualization

Start with 6 singletons and process the operations one at a time. Step forward and backward with the ← / → arrow keys or the buttons below.

The forest redraws itself after every operation — watch the trees physically merge:

Amber vertices are on the path a Find is currently walking; the cyan-highlighted vertex is the root it reaches. Every root also shows its current rank.
Green vertices were just re-linked — either a root attached under another root by Union, or a node re-pointed directly at the root by path compression.
The parent[] and rank[] arrays below track the exact state the code manipulates.

Note: rank entries become loose upper bounds after compression — they aren't recomputed. That is fine; ranks only guide unions, and the amortized bound still holds.

ElementOn the Find pathRoot (representative)Just re-linked / compressed

Ops

Union(1, 2)Union(3, 4)Union(2, 4)Find(4)Union(5, 6)Union(1, 6)

parent[]

rank[]

Start: 6 singletons — every element is its own root, all ranks 0.

1 / 19

Speed

Tip: step through with the ← / → arrow keys.

Pseudocode

All three operations in full, with both heuristics. Note how short this is — a contest-ready DSU fits in under 20 lines of C++. The one-liner find with compression and the rank comparison in unite are exactly the two tricks the visualization shows. The C++ tab runs the same operation sequence as the visualization above.

1// Disjoint-set forest with union by rank + path compression.
2
3MAKE-SET(u):
4    parent[u] = u
5    rank[u]   = 0
6
7FIND(u):
8    if parent[u] != u:
9        parent[u] = FIND(parent[u])     // path compression
10    return parent[u]
11
12UNION(u, v):
13    ru = FIND(u)
14    rv = FIND(v)
15    if ru == rv: return                  // already connected
16
17    if rank[ru] < rank[rv]:
18        parent[ru] = rv
19    else if rank[ru] > rank[rv]:
20        parent[rv] = ru
21    else:
22        parent[rv] = ru
23        rank[ru]   = rank[ru] + 1
24
25CONNECTED(u, v):
26    return FIND(u) == FIND(v)

Complexity — why α(n) ≈ 4

Without optimizations, Find is O(n) in the worst case (a chain). Each individual heuristic alone gives O(log n) per operation. Together they give the famous bound:

A sequence of m operations on n elements runs in O(m · α(n)) total time, where α is the inverse Ackermann function.

α(n) grows so slowly that α(2^65536) is still ≤ 5. For all practical inputs we can simply call this O(1) amortized.

MakeSet: O(1).
Find: O(α(n)) amortized.
Union: O(α(n)) amortized (dominated by two Finds).
Space: O(n) for the parent[] and rank[] arrays.

Complexity Analysis

Time Complexity

O(α(n)) amortized per Find or Union, where α is the inverse Ackermann function — effectively O(1). A sequence of m operations on n elements runs in O((m + n)·α(n)).

Space Complexity

O(n) for the parent[] and rank[] arrays.

Without union by rank or path compression, individual operations can take Θ(n). With either one alone, Θ(log n). With both, the inverse-Ackermann bound — never more than 4 or 5 in practice.

Growth Rate Comparison

Where union-find shows up

Every time the question "are these two things in the same group?" comes up dynamically, union-find is the right hammer:

Kruskal's MST — group endpoints of edges already added; reject an edge iff its endpoints are already united.
Cycle detection in an undirected graph as edges arrive.
Offline connectivity queries — answer "are u and v connected?" after a batch of unions.
Image / pixel grouping — connected-component labeling on grids.
Equivalence relations — group elements declared equal by a stream of equality statements.
Network connectivity and percolation simulations.

The problem it solves

Suppose you have n elements and a stream of operations of two kinds:

Union(u, v) — merge the set containing u with the set containing v.
Find(u) — return a representative of the set containing u. Two elements are in the same set iff Find(u) == Find(v).

A naive approach (one boolean matrix or one BFS per query) is far too slow. The disjoint-set forest answers both operations in essentially constant amortized time with two clever heuristics.

The structure — a forest of rooted trees

Each set is stored as a rooted tree. Every element holds one pointer: parent[u]. The root points to itself.

To find the representative of u, walk parent pointers until you hit a root. The root is the representative.

Example

Sets {1, 4, 5} and {2, 3, 6, 7}:

5 3

│ / \

4 2 6

│ │

1 7

parent: 1→4, 4→5, 5→5, 2→3, 3→3, 6→3, 7→6

Without further care, these trees can become long chains, making Find slow. Two optimizations keep them shallow:

1. Union by rank — when merging two trees, attach the shorter one under the taller one. rank[u] is an upper bound on the height of u's subtree.

2. Path compression — during Find, re-point every visited node directly to the root. Subsequent Finds along the same path become O(1).

With both, every operation runs in O(α(n)) amortized time, where α is the inverse Ackermann function — for any conceivable input, α(n) ≤ 4. So effectively constant.

The three operations

MakeSet(u) — create a singleton set: parent[u] = u, rank[u] = 0.

Find(u) — climb to the root; on the way back, compress the path:

Example

Find(u):

if parent[u] != u:

parent[u] = Find(parent[u]) // compress

return parent[u]

Union(u, v) — find both roots; if they differ, link the lower-rank tree under the higher-rank one:

Example

Union(u, v):

ru = Find(u); rv = Find(v)

if ru == rv: return // already in the same set

if rank[ru] < rank[rv]: parent[ru] = rv

else if rank[ru] > rank[rv]: parent[rv] = ru

else: parent[rv] = ru; rank[ru] += 1

Step-by-step visualization

Start with 6 singletons and process the operations one at a time. Step forward and backward with the ← / → arrow keys or the buttons below.

The forest redraws itself after every operation — watch the trees physically merge:

Amber vertices are on the path a Find is currently walking; the cyan-highlighted vertex is the root it reaches. Every root also shows its current rank.
Green vertices were just re-linked — either a root attached under another root by Union, or a node re-pointed directly at the root by path compression.
The parent[] and rank[] arrays below track the exact state the code manipulates.

Note: rank entries become loose upper bounds after compression — they aren't recomputed. That is fine; ranks only guide unions, and the amortized bound still holds.

ElementOn the Find pathRoot (representative)Just re-linked / compressed

Ops

Union(1, 2)Union(3, 4)Union(2, 4)Find(4)Union(5, 6)Union(1, 6)

parent[]

rank[]

Start: 6 singletons — every element is its own root, all ranks 0.

1 / 19

Speed

Tip: step through with the ← / → arrow keys.

Pseudocode

1// Disjoint-set forest with union by rank + path compression.
2
3MAKE-SET(u):
4    parent[u] = u
5    rank[u]   = 0
6
7FIND(u):
8    if parent[u] != u:
9        parent[u] = FIND(parent[u])     // path compression
10    return parent[u]
11
12UNION(u, v):
13    ru = FIND(u)
14    rv = FIND(v)
15    if ru == rv: return                  // already connected
16
17    if rank[ru] < rank[rv]:
18        parent[ru] = rv
19    else if rank[ru] > rank[rv]:
20        parent[rv] = ru
21    else:
22        parent[rv] = ru
23        rank[ru]   = rank[ru] + 1
24
25CONNECTED(u, v):
26    return FIND(u) == FIND(v)

Complexity — why α(n) ≈ 4

Without optimizations, Find is O(n) in the worst case (a chain). Each individual heuristic alone gives O(log n) per operation. Together they give the famous bound:

A sequence of m operations on n elements runs in O(m · α(n)) total time, where α is the inverse Ackermann function.

α(n) grows so slowly that α(2^65536) is still ≤ 5. For all practical inputs we can simply call this O(1) amortized.

MakeSet: O(1).
Find: O(α(n)) amortized.
Union: O(α(n)) amortized (dominated by two Finds).
Space: O(n) for the parent[] and rank[] arrays.

Complexity Analysis

Time Complexity

O(α(n)) amortized per Find or Union, where α is the inverse Ackermann function — effectively O(1). A sequence of m operations on n elements runs in O((m + n)·α(n)).

Space Complexity

O(n) for the parent[] and rank[] arrays.

Without union by rank or path compression, individual operations can take Θ(n). With either one alone, Θ(log n). With both, the inverse-Ackermann bound — never more than 4 or 5 in practice.

Growth Rate Comparison

Where union-find shows up

Every time the question "are these two things in the same group?" comes up dynamically, union-find is the right hammer:

Kruskal's MST — group endpoints of edges already added; reject an edge iff its endpoints are already united.
Cycle detection in an undirected graph as edges arrive.
Offline connectivity queries — answer "are u and v connected?" after a batch of unions.
Image / pixel grouping — connected-component labeling on grids.
Equivalence relations — group elements declared equal by a stream of equality statements.
Network connectivity and percolation simulations.