Union-Find

Union-Find (a.k.a. Disjoint Set Union, DSU) is a data structure that maintains a partition of n elements into disjoint sets, supporting two operations: find(x) returns a canonical representative of x’s set, and union(x, y) merges the sets containing x and y. With path compression + union by rank, both operations run in inverse Ackermann time O(α(n)) — effectively constant for any practical n. Union-Find is the secret weapon behind Kruskal’s MST, dynamic connectivity, equivalence classes, Tarjan’s offline LCA, and a swarm of “are these in the same group?” interview problems.

1. Intuition — Friend-Group Tracker

Imagine you’re at a party with 100 strangers. As people meet and become friends, they form social cliques.

• You want to ask, constantly: “Are Alice and Bob in the same friend group?”
• And: “Alice just met Carol — merge their friend groups.”

You could maintain explicit lists, but merging two groups of size m and n is O(m + n). Over many merges that’s expensive.

Union-Find’s trick: each group is represented by a tree of pointers, where everyone in the group points (eventually) to the same “root.” To check “same group?”, follow your pointer chain up to the root, and compare roots. To merge, just hang one root under the other.

The clever part: with two small optimizations (path compression + union by rank), the amortized cost per operation becomes essentially O(1) — the inverse Ackermann function α(n) is ≤ 4 for any n smaller than the number of atoms in the universe.

2. Naive Implementation

class UnionFindNaive:
    def __init__(self, n):
        self.parent = list(range(n))      # each element is its own root
 
    def find(self, x):
        while self.parent[x] != x:        # walk up to root
            x = self.parent[x]
        return x
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.parent[rx] = ry          # hang rx's tree under ry

Problem: without optimization, the trees can degenerate into long chains. A worst-case sequence of unions can produce a chain of length n, making subsequent find operations O(n). Need to fix.

3. Optimization 1 — Path Compression

When find(x) walks up to the root, update each visited node to point directly to the root. Subsequent finds on the same node (or any descendant) are now O(1).

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])    # recursive flatten
    return self.parent[x]

Iterative version (avoids recursion depth issues):

def find(self, x):
    # Phase 1: find the root
    root = x
    while self.parent[root] != root:
        root = self.parent[root]
    # Phase 2: compress — make every node on the path point directly to root
    while self.parent[x] != root:
        self.parent[x], x = root, self.parent[x]
    return root

After path compression, the tree gets flatter with every operation. The amortized cost per find rapidly approaches O(1).

4. Optimization 2 — Union by Rank (or Size)

When merging, always hang the smaller tree under the larger, so the resulting tree’s height grows only when both subtrees have equal rank. This keeps trees balanced even without path compression.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n              # upper bound on tree height
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False                  # already in same set
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

Union by size is the equivalent variant: track set sizes instead of ranks. Slightly more useful in practice because the size info is often itself useful (e.g., “size of largest connected component”). Functionally interchangeable.

5. Complexity — The Inverse Ackermann Story

With both path compression and union by rank/size:

Operation	Amortized	Worst-case single
find	O(α(n))	O(log n)
union	O(α(n))	O(log n)

Where α(n) is the inverse of the Ackermann function — a function that grows so slowly that α(n) ≤ 4 for any n we’ll ever encounter in practice. For interview purposes, say “effectively O(1) amortized”.

Without optimizations

Naive Union-Find (no path compression, no union by rank) has worst-case O(n) per operation — the famous “linked-list” degenerate case. Always include both optimizations. With only union by rank, you get O(log n) worst-case per op (which is also fine but not as tight).

The proof of O(α(n)) is one of the most beautiful — and difficult — analyses in CS. Tarjan’s 1975 paper introduced the technique. The proof intuition: each find traverses a chain whose nodes’ ranks are increasing, but the rank can grow only slowly; path compression keeps the amortized cost bounded by α(n) per operation. The full proof is a 4-page tour de force; knowing the result and not the proof is fine for interviews.

6. Tiny Worked Example

n = 6. Initial state: every element its own set.

Parent: [0, 1, 2, 3, 4, 5]
Rank:   [0, 0, 0, 0, 0, 0]

Visualization (6 separate trees, each a singleton):
0  1  2  3  4  5

union(0, 1) — both rank 0; tie → 0 becomes parent, rank[0] += 1.

Parent: [0, 0, 2, 3, 4, 5]
Rank:   [1, 0, 0, 0, 0, 0]

   0
   |
   1
2  3  4  5

union(2, 3) — same.

Parent: [0, 0, 2, 2, 4, 5]
Rank:   [1, 0, 1, 0, 0, 0]

   0      2
   |      |
   1      3
4  5

union(0, 2) — both rank 1; tie → 0 becomes parent, rank[0] += 1.

Parent: [0, 0, 0, 2, 4, 5]
Rank:   [2, 0, 1, 0, 0, 0]

      0
     / \
    1   2
        |
        3
4  5

find(3): 3 → 2 → 0. Path compression: 3’s parent becomes 0 directly.

Parent: [0, 0, 0, 0, 4, 5]
        ^^ 3 now points directly to root

      0
   /  |  \
  1   2   3
4  5

After many operations, the trees become very flat — typically depth 1 or 2 in practice.

7. Common Use Cases

7.1 Kruskal’s MST

Sort edges by weight; for each edge, add it to the MST iff its endpoints are in different components (use union to merge if so). Uses one find and one union per edge.

7.2 Dynamic Connectivity Queries

“After adding edges (a,b), (c,d), …, is x connected to y?” Process queries online with one union per edge and one find per query. Each is O(α(n)).

Adding edges is easy; removing is hard

Standard Union-Find supports union (add edge) but not disconnect (remove edge). For fully dynamic connectivity (with deletions), use Link-Cut trees or Euler tour trees — much more complex.

7.3 Cycle Detection in Undirected Graph

For each edge (u, v): if find(u) == find(v), adding this edge creates a cycle. Otherwise union(u, v) and continue. Used as preprocessing for many algorithms.

7.4 Number of Connected Components

Initialize a counter to n; decrement every time a union actually merges two distinct components.

def components_after_edges(n, edges):
    uf = UnionFind(n)
    components = n
    for u, v in edges:
        if uf.union(u, v):
            components -= 1
    return components

7.5 Equivalence Classes

Any “elements x and y are equivalent under relation R” problem can be modeled as Union-Find. Examples: “find names that refer to the same person across email aliases,” “merge accounts based on shared identifiers,” “synonym groups in word puzzles.”

7.6 Tarjan’s Offline LCA

Process LCA queries offline using a DFS + Union-Find combination, in O((n + q) α(n)) total. Beats per-query algorithms when many queries are batched. See Lowest Common Ancestor.

7.7 Percolation / Image Connected Components

Grid problems where you “fill in” cells and ask connectivity questions can use Union-Find with grid cells as elements. The “Number of Islands II” problem (LC 305) is the canonical example.

8. Variants

8.1 Weighted Union-Find (Union-Find with Weights)

Each element carries a “potential” or “offset” relative to its parent. Useful for problems like “x is k apart from y; y is m apart from z; what’s the offset between x and z?” — can be solved with weights along Union-Find edges.

8.2 Union-Find with Rollback

Some algorithms need to undo unions (e.g., offline DP on a tree of states). Standard Union-Find with path compression doesn’t support rollback. Drop path compression (use only union by rank); store a stack of (parent, rank) changes per operation; rollback by popping. Complexity: O(log n) per op.

8.3 Persistent Union-Find

Keep all historical versions of the structure. Path-copying or path-compression-with-snapshot variants exist; complex; rarely needed in interviews.

9. Common Interview Problems

Problem	Pattern
LC 547 — Number of Provinces	Connected components
LC 200 — Number of Islands	Connected components on grid (BFS/DFS often cleaner)
LC 305 — Number of Islands II	Online connected components (DSU shines here)
LC 684 — Redundant Connection	Cycle detection
LC 685 — Redundant Connection II	Cycle detection in directed (trickier)
LC 990 — Satisfiability of Equality Equations	Equivalence classes
LC 952 — Largest Component Size by Common Factor	DSU with shared-factor edges
LC 1319 — Number of Operations to Make Network Connected	Components + edge count
LC 1584 — Min Cost to Connect All Points	MST → Kruskal with DSU
LC 721 — Accounts Merge	Equivalence classes

If a problem has the words “connected,” “merge,” “same group,” “equivalent,” or “cycle” — Union-Find is on the shortlist.

10. Pitfalls

10.1 Forgetting Path Compression

The O(α(n)) bound requires path compression. Without it, you can hit O(log n) per op, which is fine but worse asymptotically.

10.2 Forgetting Union by Rank/Size

Same — without it, trees can be tall, and individual finds can be slow.

10.3 Self-Union

union(x, x) should be a no-op. Most implementations handle it correctly (the if rx == ry check), but verify.

10.4 Recursion Depth in find

Recursive find with path compression has worst-case depth equal to the tree height before compression. On worst-case naïve trees, that could be O(n). Python’s default recursion limit (1000) breaks. Use iterative find or sys.setrecursionlimit(...).

10.5 Counting Components Wrongly

If you naively count “number of distinct roots” by iterating for x in range(n): roots.add(find(x)), you trigger path compressions during the count. Functionally fine, but make sure you call find(x) (compresses) and not just parent[x] (doesn’t — gives potentially-wrong intermediate parent).

10.6 Using DSU When Order Matters

DSU treats the structure as a partition — it doesn’t distinguish “x is the parent of y” from “y is the parent of x” semantically. If your problem cares about a directed relationship, DSU loses the distinction once united.

10.7 Using DSU for Removal

Cannot. DSU does not support edge removal. Reach for Link-Cut Tree or Euler tour trees if you need that.

10.8 Initializing Wrong Size

Forgetting to size the parent and rank arrays correctly is an off-by-one bug. If your nodes are 1-indexed but you allocate [0..n-1], the n-th node is invalid. Check.

11. Diagram — Path Compression in Action

flowchart TD
  subgraph "Before find(D)"
    A1[A root] --> B1[B]
    B1 --> C1[C]
    C1 --> D1[D]
  end
  subgraph "After find(D) with path compression"
    A2[A root]
    A2 --> B2[B]
    A2 --> C2[C]
    A2 --> D2[D]
  end

What this diagram shows. A find(D) walk traverses D → C → B → A. After the walk, all visited nodes (D, C, B) are made to point directly to the root A. Subsequent find(D), find(C), or find(B) are O(1). Path compression aggressively flattens the tree, which is why the amortized cost stays so low.

12. Implementation Quality Checklist

For interviews, your DSU should:

• ✅ Support find(x) with path compression (recursive or iterative)
• ✅ Support union(x, y) with union by rank or size
• ✅ Return whether union actually merged (for component-count maintenance)
• ✅ Optionally expose connected(x, y) as find(x) == find(y) for readability
• ✅ Optionally maintain count (number of components) for O(1) component-count queries

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n                     # number of components
 
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]    # halving (alternative)
            x = self.parent[x]
        return x
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        self.count -= 1
        return True
 
    def connected(self, x, y):
        return self.find(x) == self.find(y)

The path-halving variant in find (point each node to its grandparent during the walk) is a simpler alternative to full path compression with similar asymptotic guarantees and zero recursion. Worth knowing.

13. Open Questions

• Is α(n) the absolute optimum? Yes — Fredman & Saks (1989) proved a matching lower bound: any DSU with n operations has amortized Ω(α(n)) per op.
• When does path-halving beat full path-compression in practice? Generally a wash; halving is slightly cleaner code.

14. See Also

• Kruskal’s Algorithm — DSU is its core data structure
• Connected Components — DSU vs BFS/DFS trade-offs
• Strongly Connected Components — Tarjan offline LCA uses DSU
• Lowest Common Ancestor — Tarjan offline LCA
• Amortized Analysis — for O(α(n)) justification
• Big-O Notation
• SWE Interview Preparation MOC