SpecializedData structureaka DSU, disjoint set, merge-find set

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.

▶ VisualizePattern: Union-FindPractice (4)
Progress

Definition

Union-Find maintains a collection of disjoint sets over elements 0…n-1 and supports two operations: find(x) returns a canonical representative of the set containing x, and union(x, y) merges the sets containing x and y. Two elements are in the same set iff find(x) == find(y).

Each set is a rooted tree stored in a parent[] array; the root is the representative. Two heuristics — path compression (point every visited node straight at the root during find) and union by rank/size (attach the shorter tree under the taller) — bring the amortized cost per operation to O(α(n)), where α is the inverse Ackermann function, ≤ 4 for any conceivable n.

It is the backbone of Kruskal's Algorithm, the fastest way to answer incremental connectivity ("after adding these edges, are u and v connected?"), and the standard tool for Cycle Detection in undirected graphs, Connected Components counting, and equivalence-class grouping (accounts merge, similar strings, equations satisfiability).

disjoint setsconnectivityinverse Ackermannpath compressionunion by rankKruskal

Intuition

A mental model before the formal terms.

Every person starts as the leader of their own one-person club. When two clubs merge, one leader agrees to report to the other. To find out which club someone belongs to, follow the chain of "who do you report to?" until you hit someone who reports to themselves — the leader.

Path compression: once you have walked the chain, tell everyone on it who the leader is so next time they answer immediately. Union by rank: when merging, the smaller hierarchy joins under the bigger one so chains never get long. Together, chains stay so short that each question is effectively instant.

How it works

  1. Init: parent[i] = i, rank[i] = 0 (or size[i] = 1), count = n sets.
  2. find(x): walk x → parent[x] until parent[r] == r. On the way back, set parent[node] = r for every node visited (path compression). Iterative variant: path halving — parent[x] = parent[parent[x]] at each step.
  3. union(x, y): rx = find(x), ry = find(y). If equal, return false (already connected — this is the cycle signal). Otherwise attach the root with smaller rank under the other; if ranks tie, pick either and increment its rank. Decrement count. Return true.
  4. connected(x, y): find(x) == find(y).
  5. Union by size is an equivalent alternative: attach the smaller set under the larger and add sizes; it also gives you set sizes for free.
  6. Extensions: store per-set aggregates at the root (sum, min, count of edges), or a weighted DSU that tracks the offset from each node to its root for "x is d more than y" constraints.

Why it works

Union by rank guarantees a root of rank r has at least 2^r descendants, so tree height is ≤ log₂ n even without compression, giving O(log n) per operation.

Path compression flattens trees aggressively; Tarjan proved the combination yields O(m · α(n)) total for m operations, where α(n) ≤ 4 for n < 10^600. Practically constant.

Because union returns false exactly when both endpoints already share a root, processing an undirected graph's edges in order detects the first edge that closes a cycle.

Operations

OperationDescriptionCost
find(x)Return the root representative of x, compressing the path.O(α(n)) amortized
union(x, y)Merge the sets of x and y by rank; return false if already merged.O(α(n)) amortized
connected(x, y)find(x) == find(y).O(α(n)) amortized
count()Number of disjoint sets.O(1)
size(x)Size of the set containing x (union by size variant).O(α(n)) amortized
reset / add elementAppend a new singleton.O(1)

Recognition

How to tell a problem wants this.

  • "Are u and v connected?" after a sequence of edge additions (never removals).
  • "Number of connected components / provinces / groups / islands" with edges given as pairs.
  • "Merge accounts / equivalent characters / similar groups" — any equivalence relation.
  • Minimum spanning tree (Kruskal's Algorithm) or "redundant connection" / cycle in an undirected graph.
  • Offline queries that can be processed in sorted order (e.g. "number of pairs reachable with edge weight ≤ k").
“connected groups” → Union-Find

Interactive demo

Play, step, change the input. ← → and space work too.

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

Pseudocode

1init: parent[i] = i; rank[i] = 0; count = n
2find(x): while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]; return x
3union(x, y):
4  rx, ry = find(x), find(y); if rx == ry: return false
5  if rank[rx] < rank[ry]: swap(rx, ry)
6  parent[ry] = rx; if rank[rx] == rank[ry]: rank[rx] += 1
7  count -= 1; return true

Implementation

1class UnionFind:
21 · State — parent, rank and set size per node
3    def __init__(self, n: int):
4        self.parent = list(range(n))  # every node is its own root
5        self.rank = [0] * n
6        self.size = [1] * n
7        self.count = n
8 
92 · Find with path compression (iterative, two passes)
10    def find(self, x: int) -> int:
11        root = x
12        while self.parent[root] != root:
13            root = self.parent[root]
14        while self.parent[x] != root:  # second pass: point every node on the path at the root
15            self.parent[x], x = root, self.parent[x]
16        return root
17 
183 · Union by rank
19    def union(self, x: int, y: int) -> bool:
20        rx, ry = self.find(x), self.find(y)
21        if rx == ry:
22            return False  # already in the same set
23        if self.rank[rx] < self.rank[ry]:
24            rx, ry = ry, rx  # attach the shorter tree under the taller
25        self.parent[ry] = rx
26        self.size[rx] += self.size[ry]
27        if self.rank[rx] == self.rank[ry]:
28            self.rank[rx] += 1
29        self.count -= 1
30        return True
31 
324 · Queries
33    def connected(self, x: int, y: int) -> bool:
34        return self.find(x) == self.find(y)
35 
36    def set_size(self, x: int) -> int:
37        return self.size[self.find(x)]
Walkthrough
  1. list(range(n)) is the identity parent list; [0] * n and [1] * n initialise rank and size.
  2. find walks to the root, then the tuple assignment self.parent[x], x = root, self.parent[x] compresses the path in one line — the right-hand side is evaluated before either target is assigned.
  3. union swaps rx, ry with tuple unpacking so the taller tree stays the root.
  4. Rank grows only on equal-rank merges; count is decremented on each successful union.
  5. set_size reads size at the root found by find.
Complexity (this implementation)
time O(α(n)) amortized per operation · space O(n)
Language notes
  • Python has no stdlib disjoint-set; networkx.utils.UnionFind exists if you already depend on networkx.
  • Iterative find matters more in Python: the default recursion limit is 1000 and recursive calls are slow.
  • Tuple assignment evaluates the whole right side first, which is what makes the one-line path-compression step correct.
  • For hashable non-integer keys, replace the lists with dicts and use setdefault(x, x) on first sight.
Common mistakes in this language
  • Writing the compression as two separate statements in the wrong order (x = self.parent[x] before rewriting parent[x]) so the original parent is lost.
  • Naming the method union on a set subclass — clashes with set.union.
  • Using recursion for find and hitting RecursionError on adversarial chains before compression.
Language differences that matter here
  • union is a keyword in C++, so the C++ method is unite; JS/TS/Python can use union freely.
  • Recursive find is idiomatic in C++ (deep stacks are cheap) but risky in Python (recursion limit 1000) and JS (engine-dependent limit around 10k frames); the iterative two-pass form is safe everywhere.
  • Python tuple assignment lets path compression be a one-liner; C++/JS/TS need a temporary next.
  • Only C++ has a fixed-width int; JS/TS use doubles (safe up to 2^53) and Python ints are unbounded — irrelevant for indices but relevant if you store aggregated weights per set.

Complexity

OperationAverageWorstNote
Access——No positional access.
SearchO(α(n))O(log n)Find representative; amortized α(n).
InsertO(1)O(1)Add a singleton.
Delete——Not supported without rollback/offline techniques.
UpdateO(α(n))O(log n)Union.
FindO(α(n))O(log n)
UnionO(α(n))O(log n)
ConnectedO(α(n))O(log n)
Count setsO(1)O(1)
SpaceO(n)α(n) ≤ 4 for all practical n; worst case per single call is O(log n) with union by rank.

Advantages & disadvantages

Advantages
  • Near-constant amortized time per operation with ~20 lines of code.
  • Tiny memory footprint: two integer arrays.
  • Processes edges online — no need to know the whole graph in advance.
  • Naturally reports cycles and component counts as a by-product.
Disadvantages
  • No un-union: deleting an edge requires rebuilding or an offline/rollback variant (without path compression).
  • Cannot enumerate the members of a set without an auxiliary structure.
  • Only models undirected connectivity — direction and path lengths are lost.
  • Recursive find can overflow the stack on 10^6-element chains before compression kicks in; use the iterative form.

Use cases

  • Kruskal's Algorithm minimum spanning tree.
  • Counting Connected Components in a graph given as an edge list.
  • Redundant Connection: the first edge whose union fails.
  • Accounts Merge, Similar String Groups, Satisfiability of Equality Equations.
  • Percolation, image segmentation, and Kruskal-style clustering.
  • Offline dynamic connectivity and "number of islands II" (incremental grid additions).
Use it when
  • Dynamic connectivity with only additions of edges.
  • Counting components or detecting a cycle in an undirected graph given as edges.
  • Kruskal's MST.
  • Grouping by an equivalence relation (merge accounts, equal-equations).
  • Offline processing of queries sorted by threshold.
Avoid it when

Alternatives

Connected ComponentsDepth-First Search (DFS)Breadth-First Search (BFS)Adjacency List
Compare: Union-Find vs DFS

Common mistakes

  • Skipping both heuristics — a plain linked chain makes find O(n).
  • Comparing x == y instead of find(x) == find(y) to test connectivity.
  • Setting parent[y] = x instead of parent[find(y)] = find(x) — attaches a non-root and corrupts the forest.
  • Recursive find without compression on large inputs — stack overflow in Python.
  • Forgetting to map arbitrary labels (strings, emails) to 0…n-1 indices first.
  • Using DSU on a directed graph to answer reachability.

Interview patterns

  • Number of Connected Components / Provinces: count after unions.
  • Redundant Connection: first edge whose union returns false.
  • Accounts Merge: union emails, then group by root.
  • Min Cost to Connect All Points: Kruskal.
  • Number of Islands II: incremental grid cells with union of neighbors.
  • Longest Consecutive Sequence: union x with x + 1 and track set sizes.
  • Satisfiability of Equality Equations: union == pairs, then check every !=.
Interview questions on this
Mock interviews

Interview problems

Number of IslandsmediumNumber of Connected ComponentsmediumMin Cost to Connect All PointsmediumRedundant Connectionmedium