Overview

Union-Find maintains a collection of disjoint groups. It supports two operations: find(x) returns a representative of x's group, and union(a, b) merges the groups containing a and b. Each group is stored as a tree of parent pointers, and the representative is the root.

Two small optimisations make it astonishingly fast. Path compression flattens the tree every time you call find, and union by size (or rank) always hangs the smaller tree under the larger one. Together they bring the amortised cost to O(α(n)), where α is the inverse Ackermann function — at most 4 for any input that fits in the universe.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
find / union (both optimisations)O(α(n)) amortised ≈ O(1)
Without optimisationsO(n) per operation worst case
Kruskal's MSTO(E log E) — dominated by sorting

Patterns to recognise

Dynamic connectivity

Use it for: Number of provinces, network connected, redundant connection.

Union every edge; query or count components afterwards.

Equivalence grouping

Use it for: Accounts merge, satisfiability of equations, similar strings.

Union things that are "equal", then check or collect groups by root.

Minimum spanning tree

Use it for: Min cost to connect all points.

Sort edges, union greedily, stop after V − 1 edges.

Code template

Disjoint Set Union with path compression and union by size
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra             # smaller tree under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

Common mistakes

  • Setting parent[a] = b instead of linking the roots corrupts the structure.
  • Map non-integer identifiers (emails, strings) to integer ids first, or use a dictionary-based DSU.
  • Union-Find answers connectivity in undirected graphs; it cannot handle edge deletions or directed reachability.

Quick check

Three questions on Union-Find. Get all three right to earn +15 XP.

  1. What does find(x) return?

  2. What does path compression do?

  3. While adding edges of an undirected graph, when does Union-Find signal a cycle?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Union-Find?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor