Union-Find (Disjoint Set Union): Near-Constant Connectivity with Two Optimizations

Union-find (also called disjoint-set union, or DSU) solves one specific problem astonishingly well: maintaining a collection of disjoint groups under two operations — find (which group is x in?) and union (merge the groups of x and y). It's how Kruskal's algorithm detects cycles, how you count connected components in a graph as edges arrive, and how many 'are these connected?' problems get their speed. Small structure, huge payoff — and a genuinely beautiful complexity result.

In plain words — merging friend groups

Think of a social network where people start as strangers. Each person is their own group. When two people become friends, their groups merge — and all the people who were friends with either of them are now in the same group. The question 'are Alice and Bob in the same friend group?' is the find question. Merging two groups is the union question. Union-find is the data structure that answers both, fast, as the social graph grows dynamically edge by edge.

The idea: each group is a tree, named by its root

Represent each element as a node with a parent pointer. Every group is a tree; the group's identity is its root (a node that points to itself). To find which group x belongs to, follow parent pointers up to the root. To union two groups, make one group's root point to the other's — one pointer change merges them. Two elements are in the same group iff they share a root, so 'are x and y connected?' is just 'find(x) == find(y)?'.

1. makeSet(x): parent[x] = x (each element starts as its own singleton group).
2. find(x): while parent[x] ≠ x, move to parent[x]; return the root.
3. union(x, y): r1 = find(x), r2 = find(y); if different, set one root's parent to the other.

Initial state (5 nodes 0..4, each its own root):
parent: [0, 1, 2, 3, 4]
rank:   [0, 0, 0, 0, 0]

After union(0, 1):
  find(0)=0, find(1)=1 → different → parent[1] = 0
  parent: [0, 0, 2, 3, 4]
  Tree:   0        2   3   4
          |
          1

After union(2, 3):
  find(2)=2, find(3)=3 → parent[3] = 2
  parent: [0, 0, 2, 2, 4]
  Trees:  0        2   4
          |        |
          1        3

After union(1, 2):
  find(1) → parent[1]=0 → root=0
  find(2) → parent[2]=2 → root=2
  different → parent[2] = 0
  parent: [0, 0, 0, 2, 4]
  Tree:   0              4
         / \
        1   2
            |
            3

Now find(3): 3→2→0. Three hops.
(Without path compression, long chains are possible.)

The catch: naively, unions can build long, spindly trees (chain everything together and find walks the whole chain → O(n)). Two optimizations fix this — and together they make the structure nearly free.

Optimization 1: union by rank (or size)

When merging two trees, always attach the *shorter* tree under the taller one's root (rank ≈ tree height), or the *smaller* tree under the larger (by size). This keeps trees shallow: attaching a short tree under a tall one doesn't increase height, so heights grow only when two equal-height trees merge — logarithmically at most. Alone, this bounds find at O(log n).

Two trees, each rank 1:
  Tree A (root=0, rank=1):    Tree B (root=2, rank=1):
      0                            2
     / \                          / \
    1   4                        3   5

union(0, 2): both rank=1 → attach B under A, increment rank of A
  parent[2] = 0, rank[0] = 2

Result (rank=2):
        0
      / | \
     1  4   2
           / \
          3   5

find(5): 5→2→0. Only 2 hops even for 6 nodes.
Height grows to log₂(n) in the worst case — never a long chain.

Optimization 2: path compression

During a find, after locating the root, point every node on the path directly at the root. The next find on any of those nodes is then O(1). Path compression flattens trees aggressively as a side effect of the queries themselves — the more you use the structure, the flatter it gets. One-line change (repoint as you unwind the find recursion), enormous effect.

BEFORE find(6):
   0 (root)
   |
   1
   |
   2
   |
   3
   |
   6    ← find(6) walks: 6→3→2→1→0 (4 hops)

Path compression: on the way back up the recursion,
set parent of every visited node directly to root (0):
   parent[6] = 0
   parent[3] = 0
   parent[2] = 0
   parent[1] = 0

AFTER find(6):
   0 (root)
  /|\\
 1 2 3 6   ← all point directly to root

Next find(6): 6→0. 1 hop.
Next find(3): 3→0. 1 hop.
The tree is now nearly flat for all future queries.

The inverse-Ackermann bound

Apply *both* optimizations and something remarkable happens: any sequence of m operations runs in O(m · α(n)), where α(n) is the inverse Ackermann function. The Ackermann function grows so explosively that its inverse grows almost imperceptibly — α(n) ≤ 4 for any n up to the number of atoms in the universe. So amortized per-operation cost is, for all practical purposes, a small constant. This near-constant bound is one of the most celebrated results in data-structure theory (Tarjan, 1975), and it's why union-find feels 'free' in practice.

Complexity summary

Space is O(n) — just the parent array plus a rank/size array. Note union-find's key limitation: it supports *merging* groups but not *splitting* them. Once two groups are unioned, there's no efficient un-union. Problems that need to remove connections require different approaches (or processing operations in reverse).

Worked example: counting connected components

Given n nodes and a list of edges, how many connected components are there? Start with n singleton sets (count = n). For each edge (u, v): if find(u) ≠ find(v), they're in different components — union them and decrement count. If they're already connected, the edge is redundant (it would form a cycle — exactly Kruskal's cycle test).

Initial: parent=[0,1,2,3], count=4

Edge (0,1): find(0)=0, find(1)=1 → different
  union(0,1): parent[1]=0, count=3
  parent=[0,0,2,3]

Edge (2,3): find(2)=2, find(3)=3 → different
  union(2,3): parent[3]=2, count=2
  parent=[0,0,2,2]

Edge (1,2): find(1)→parent[1]=0→root=0
            find(2)→parent[2]=2→root=2 → different
  union(0,2): parent[2]=0, count=1
  parent=[0,0,0,2]

Final count: 1  (all nodes connected)
Verify: find(3)→parent[3]=2→parent[2]=0 → root 0.
        find(1)→parent[1]=0 → root 0. Same group. ✓

Applications

• Kruskal's MST: Process edges cheapest-first; use union-find to skip edges that would create a cycle. The cycle test is find(u) == find(v).
• Dynamic connectivity: As edges arrive in a stream, answer 'are u and v connected yet?' in near-O(1) after each edge.
• Image labeling: Connected-pixel region detection (flood-fill variant) — merge adjacent same-color pixels.
• Network percolation: Determine when enough links exist for a connected path across a grid.
• Equivalence grouping: 'Are these two user accounts the same person?' Merge on evidence, query for group membership.
• Redundant connection: Given a tree plus one extra edge, find the extra edge — it's the first edge where find(u)==find(v).

Common pitfalls

• Skipping the optimizations. Naive union-find is O(n) per operation and defeats the purpose. Always use path compression + union by rank/size; it's a few extra lines for an exponential improvement.
• Comparing parents instead of roots. Two elements are in the same set iff they share a *root*, not a parent. Always call find() (which walks to the root) — checking immediate parents is wrong.
• Expecting to un-union. Union-find merges only; it can't efficiently split groups. If you need deletions, rethink the approach.
• Forgetting to update the count/rank on union. Component counts and ranks must be maintained *inside* union, only when roots actually differ.
• Union-ing without checking roots first. Always find both roots and act only if they differ, or you corrupt ranks and miscount components.

Practice problems

• Number of Provinces: Given an adjacency matrix, count connected components. Classic union-find setup.
• Accounts Merge: Given lists of email addresses belonging to accounts, merge accounts that share an email. Union-find where emails are elements and shared emails trigger union.
• Satisfiability of Equality Equations: Given equations like a==b and a!=b, decide if they're satisfiable. Union-find for equalities, then verify inequalities.

Key takeaways

• Union-find maintains disjoint groups with find (which group?) and union (merge groups), each near-O(1).
• Groups are trees identified by their root; same root means same group.
• Two optimizations — union by rank/size and path compression — flatten the trees; together they give O(α(n)) ≈ O(1) amortized.
• The inverse-Ackermann bound (α ≤ 4 for any realistic n) is why union-find feels free.
• It merges but never splits; use it for connectivity, cycle detection (Kruskal), component counting, and equivalence grouping.

One lesson remains on the theory side before we talk practice: why some problems (like 0/1 knapsack and many backtracking targets) seem to have no fast algorithm at all — complexity classes and P vs NP. Drill union-find in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play