Union-Find (Disjoint Set Union)

The mental model: a messy family tree

Each group is a tree. The root of the tree is the group's representative — its "ID." Every node knows its parent. To ask "what group is node x in?" you climb up parent pointers until you hit a root (a node that is its own parent). To merge two groups, you make one root the parent of the other.

Start naive: everyone's own parent.

parent: [0, 1, 2, 3, 4]
index:   0  1  2  3  4

Union(0, 1): make 0 the parent of 1. Union(1, 2): make 0 the parent of 2 (after finding 0 is 1's root). Union(3, 4): make 3 the parent of 4.

Two components now: {0, 1, 2} and {3, 4}.

flowchart TD
    A0["0 (root)"]
    A1["1"]
    A2["2"]
    B3["3 (root)"]
    B4["4"]
    A0 --> A1
    A0 --> A2
    B3 --> B4
    style A0 fill:#7c5cff,color:#fff
    style B3 fill:#22d3ee,color:#0a0a0f

find(2) walks 2 → 0 and returns 0. find(4) walks 4 → 3 and returns 3. connected(2, 4) compares 0 ≠ 3: false. Union(2, 4) merges them — now one component with root 0.

This is correct. But naive union-find has a fatal flaw: if you always union in one direction, the tree becomes a chain. find on the deepest node walks the entire chain — O(n) per operation, O(n²) total for n unions. The fix is two optimizations. Together they're the whole magic.

The two optimizations that make it fast

1. Union by rank

When merging two trees, always attach the shorter one under the taller root. "Rank" tracks an upper bound on tree height — it's not the exact height, just a conservative estimate.

def union(self, a, b):
    root_a = self.find(a)
    root_b = self.find(b)
    if root_a == root_b:
        return False   # already same component

    # attach shorter tree under taller root
    if self.rank[root_a] < self.rank[root_b]:
        root_a, root_b = root_b, root_a
    self.parent[root_b] = root_a
    if self.rank[root_a] == self.rank[root_b]:
        self.rank[root_a] += 1
    return True

Why does this keep trees shallow? Because a tree of rank r must contain at least 2^r nodes — you can prove this by induction. If the tree has rank r, it was formed by merging two trees of rank r-1, each with at least 2^(r-1) nodes. So the tree has at least 2^r. That means rank ≤ log₂(n), and find walks at most log n steps. With union by rank alone, you're at O(log n) per operation — already good.

2. Path compression

During find, as you climb from node to root, rewire every node you touch to point directly at the root:

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

One line. The recursive call finds the root; the assignment flattens the path. Next time any node on that path calls find, it's a single hop to the root.

flowchart LR
    subgraph "Before find(4)"
        direction TB
        R0["0 (root)"] --> N1["1"] --> N2["2"] --> N3["3"] --> N4["4"]
    end
    subgraph "After find(4) — path compressed"
        direction TB
        R0b["0 (root)"]
        R0b --> N1b["1"]
        R0b --> N2b["2"]
        R0b --> N3b["3"]
        R0b --> N4b["4"]
    end
    style R0 fill:#7c5cff,color:#fff
    style R0b fill:#7c5cff,color:#fff
    style N4 fill:#00ff9d,color:#0a0a0f
    style N4b fill:#00ff9d,color:#0a0a0f

The tree on the left is the chain that union by rank prevents — but path compression fixes even that case. After one find(4), the entire chain collapses to depth 1.

Together: inverse-Ackermann

Combine both optimizations and the amortized cost per operation is O(α(n)), where α is the inverse-Ackermann function. α(n) is the answer to "how many times can I apply the Ackermann function before exceeding n?" It grows so ludicrously slowly that α(2^65536) = 5. For n up to 10^80 — more atoms than the observable universe — α(n) ≤ 5. You treat it as O(1) and feel no guilt about it.

The formal proof is in Tarjan's 1975 paper. The practical takeaway: just use both optimizations and call each operation constant.

The complete implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # every node is its own parent
        self.rank = [0] * n           # all trees start at rank 0
        self.components = n           # track component count

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

    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False   # same component, no merge needed

        # union by rank: attach smaller tree under larger root
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1

        self.components -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def num_components(self):
        return self.components

This is the template. Copy it into your interview and you're 80% done. The rest is figuring out what nodes and edges to feed it.

Complexity table

Operation	Time	Space
__init__(n)	O(n)	O(n)
find(x)	O(α(n)) amortized	O(α(n)) stack
union(a, b)	O(α(n)) amortized	O(1)
connected(a, b)	O(α(n)) amortized	O(1)
m operations total	O(m · α(n))	O(n)

For comparison: a naive union-find (no optimizations) is O(n) per find. Union by rank alone is O(log n). Both together is O(α(n)). The jump from O(log n) to O(α(n)) is the path-compression win.

Worked problems

Problem 1: Number of connected components

Given n nodes and a list of undirected edges, count the components.

This is Union-Find in its purest form.

def count_components(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        uf.union(a, b)
    return uf.num_components()

One pass over edges, each union is O(α(n)), done. The BFS alternative re-scans the graph — same O(V+E) complexity but with higher constant and no dynamic-update support. Prefer Union-Find whenever the graph is built incrementally.

Problem 2: Redundant connection (LeetCode 684)

Given a graph that starts as a tree and has exactly one extra edge added, find the redundant edge.

The tell: the first edge whose two endpoints are already connected before you process it is the cycle-creating edge.

def find_redundant_connection(edges):
    n = len(edges)
    uf = UnionFind(n + 1)  # nodes are 1-indexed

    for a, b in edges:
        if not uf.union(a, b):
            return [a, b]  # union returned False → already connected → cycle

    return []

union returns False only when find(a) == find(b) — the two nodes are already in the same component, so this edge creates a cycle. Processing edges in order guarantees we return the last such edge — the one the problem says is redundant.

Time: O(n · α(n)). Space: O(n).

{ "type": "graph", "title": "redundant edge creates a cycle — spot it with union-find" }

Process each edge. The moment union returns false, you've found the edge that closes a cycle. No DFS needed, no visited tracking — one pass, nearly O(n).

Problem 3: Accounts merge (LeetCode 721)

This is Union-Find on strings, which trips people up because they reach for a graph + DFS.

Given a list of accounts where each account is [name, email1, email2, ...], merge accounts that share at least one email. Return the merged accounts with emails sorted.

The key insight: emails are the nodes. Two emails in the same account are in the same component. Union every email in an account to the first email of that account.

from collections import defaultdict

def accounts_merge(accounts):
    parent = {}

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb

    email_to_name = {}

    for account in accounts:
        name = account[0]
        # initialize each email as its own parent
        for email in account[1:]:
            if email not in parent:
                parent[email] = email
            email_to_name[email] = name
        # union all emails in this account to the first
        for email in account[2:]:
            union(account[1], email)

    # group emails by their root
    components = defaultdict(list)
    for email in parent:
        components[find(email)].append(email)

    result = []
    for root, emails in components.items():
        result.append([email_to_name[root]] + sorted(emails))

    return result

The trick: you don't need numeric indices. The parent dict works directly on string keys. This is a common adaptation — Union-Find with a hash map instead of an array when your nodes aren't consecutive integers.

Problem 4: Kruskal's minimum spanning tree

Union-Find is the engine inside Kruskal's MST algorithm. You want the cheapest set of edges that connects all nodes.

Strategy: sort edges by weight, add each edge if it connects two different components (i.e., doesn't create a cycle). Stop when you have n-1 edges.

def kruskal_mst(n, edges):
    # edges: list of (weight, u, v)
    edges.sort()
    uf = UnionFind(n)
    mst_weight = 0
    mst_edges = []

    for weight, u, v in edges:
        if uf.union(u, v):        # False means same component → skip
            mst_weight += weight
            mst_edges.append((u, v))
            if len(mst_edges) == n - 1:
                break             # MST complete

    return mst_weight, mst_edges

The cycle detection is exactly what Union-Find does for free: union returns False when both endpoints are already connected. Sorting edges is O(E log E). Each union/find is O(α(n)). Total: O(E log E), which is optimal for comparison-based MST. See also topological sort for another graph ordering algorithm with a similar "process edges in a controlled order" structure.

The patterns that signal Union-Find

You've been doing a BFS or DFS in your interviews when Union-Find would be cleaner. Here's the tell:

Problem says...	Reach for...
"number of connected components"	Union-Find
"detect a cycle in an undirected graph"	Union-Find
"merge accounts / identities / groups"	Union-Find
"minimum spanning tree"	Union-Find (Kruskal)
"add edges one at a time, query connectivity"	Union-Find
"are X and Y in the same group?"	Union-Find
"grid problems: count islands, flood-fill variants"	BFS/DFS or Union-Find

The grid question deserves elaboration. DFS patterns on a grid are fine — often simpler to code. But if the grid is enormous and connectivity queries come in batches after partial construction, Union-Find is faster because it doesn't re-traverse.

Pitfalls and anti-patterns

Forgetting to call find before comparing parents. Never compare parent[a] == parent[b] directly. Two nodes can be in the same component with different parent values — you need to find the root. Always find(a) == find(b).

Using union by size instead of rank incorrectly. Both work. Union by size (count of nodes, not estimated height) is equally valid and some people find it more intuitive. Pick one and stick to it — mixing them in a single implementation is a common source of subtle bugs.

Re-initializing UnionFind inside an inner loop. If your outer loop is over test cases and your inner loop processes edges, initialize once per test case, not once per edge. This sounds obvious but shows up constantly under interview pressure.

Calling union when you only need find. union(a, b) should only be called when you want to permanently merge two groups. If you're answering a read-only query, call connected(a, b) (two finds). Calling union accidentally merges groups you didn't intend to merge — and there's no undo.

Off-by-one in 1-indexed problems. LeetCode graph problems often give nodes numbered 1 to n. Your parent array needs size n+1. This bites a lot of people who initialize UnionFind(n) and then wonder why node n is out of bounds.

Trying to split a component. Union-Find only merges — it can't split a group once merged. If you need dynamic connectivity with both adds and removals, look at link-cut trees. They're significantly more complex and rarely asked in interviews.

When NOT to use Union-Find

Union-Find is not a graph search algorithm. It tells you whether two nodes are connected, not how they're connected, what path exists between them, or what the shortest path is.

You need	Use instead
Shortest path between two nodes	BFS (unweighted), Dijkstra (weighted)
All paths between two nodes	DFS with backtracking
Topological ordering of a DAG	Topological sort
Strongly connected components	Tarjan's / Kosaraju's algorithm
Detect cycle in a directed graph	DFS with color marking — Union-Find gets this wrong for directed edges
Split / remove connections	Link-cut trees (not an interview topic)
Minimum spanning tree with frequent edge-weight updates	Prim's algorithm may be more natural

That directed-graph gotcha is worth repeating. Union-Find treats all edges as undirected. If you feed it a directed graph's edges, it will happily merge components that aren't actually mutually reachable. For cycle detection in a directed graph, DFS with a three-color visited array is the right tool. See DFS patterns for that.

Also: if the graph is static and you need component membership once, a single BFS or DFS pass is O(V+E) and simpler to write. Union-Find's advantage is dynamic updates — if there are no updates, the overhead isn't buying you anything.

---

Union-Find is one of the few data structures where understanding the theory directly makes you faster in practice. Path compression and union by rank aren't just academic niceties — without them you have an O(n²) algorithm wearing an O(1) costume. Learn both optimizations cold, memorize the template above, and you'll recognize the "are these two things connected?" shape in problems that superficially look nothing like a graph. The accounts merge problem doesn't scream "union-find" until you've seen it once. After that, it's obvious every time.