Union-Find / Disjoint Set Union (DSU)¶

Difficulty: Medium | Pattern Type: Dynamic connectivity

← DSA Overview | ← Graph Algorithms | Next: Backtracking →

Why This Data Structure Exists¶

Some problems only ask one question, over and over, as edges stream in: "are these two things in the same group?" Recomputing connected components with BFS/DFS after every new connection is O(V+E) each time. Union-Find answers both "which group is X in?" and "merge these two groups" in near O(1) amortized, making it the right tool whenever connectivity changes incrementally.

It underlies Kruskal's MST (reject an edge if it would cycle), cycle detection in undirected graphs, "number of islands II" (dynamic grid connectivity), and friend-circle / account-merging style problems.

Mental Model¶

Each element starts as its own set (its own tree, pointing to itself). Union merges two trees by making one root point to the other. Find walks parent pointers up to the root — the root is the set's identity.

Initial:  0  1  2  3  4     (5 singleton sets, each its own root)

union(0,1): 1 → 0           union(2,3): 3 → 2
    0            0
    |            |
    1            1     2
                       |
                       3

union(1,2): root(1)=0, root(2)=2 → union by rank (equal rank → attach one root
            under the other and increment rank; rank is a height bound, not size)

    0
   / \
  1   2
      |
      3

Two optimizations turn "walk to the root" from O(n) worst case into practically O(1):

• Union by rank: attach the lower-rank root under the higher-rank root (rank bounds height, not node count). Equal rank → increment. Union by size is the different rule that attaches the smaller tree.
• Path compression: while walking up during find, repoint every visited node directly to the root, so the next find on any of them is instant.

Together they give O(α(n)) amortized per operation, where α is the inverse Ackermann function — for any input size that fits in the universe, α(n) ≤ 4. It is, for all practical purposes, constant time.

Interactive Union-Find Visualizer¶

Watch the edges flatten after a few unions — that's path compression collapsing multi-hop chains into direct root pointers.

Implementation¶

class UnionFind:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))  # each node is its own root initially
        self.rank = [0] * n           # upper bound on tree height
        self.count = n                # number of disjoint sets

    def find(self, x: int) -> int:
        """Path compression: repoint every node on the path directly to the root."""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # recursive compression
        return self.parent[x]
        # Time: O(α(n)) amortized

    def union(self, a: int, b: int) -> bool:
        """Union by rank. Returns False if a and b were already connected."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False  # already in the same set — this edge would create a cycle

        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True
        # Time: O(α(n)) amortized

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)
        # Time: O(α(n))

Iterative find (avoids recursion depth issues on adversarial inputs):

def find_iterative(parent: list[int], x: int) -> int:
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:       # second pass: compress the path
        parent[x], x = root, parent[x]
    return root
    # Time: O(α(n)) amortized, no recursion stack

When to Use Which¶

Common Problems and Patterns¶

Number of Provinces (Friend Circles)¶

def find_circle_num(is_connected: list[list[int]]) -> int:
    n = len(is_connected)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j] == 1:
                uf.union(i, j)
    return uf.count
    # Time: O(n² · α(n))  Space: O(n)

Redundant Connection (Find the Cycle-Causing Edge)¶

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    """First edge whose union() fails (already connected) is the one creating the cycle."""
    n = len(edges)
    uf = UnionFind(n + 1)  # nodes are 1-indexed
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]
    return []
    # Time: O(E · α(n))

Accounts Merge¶

from collections import defaultdict

def accounts_merge(accounts: list[list[str]]) -> list[list[str]]:
    """Union accounts that share any email; group emails by root account index."""
    uf = UnionFind(len(accounts))
    email_to_acc: dict[str, int] = {}

    for i, account in enumerate(accounts):
        for email in account[1:]:
            if email in email_to_acc:
                uf.union(i, email_to_acc[email])
            else:
                email_to_acc[email] = i

    grouped: dict[int, set[str]] = defaultdict(set)
    for email, acc_idx in email_to_acc.items():
        grouped[uf.find(acc_idx)].add(email)

    return [[accounts[root][0]] + sorted(emails) for root, emails in grouped.items()]
    # Time: O(n · α(n)) plus O(n log n) for sorting emails within each group

Complexity Summary¶

α(n), the inverse Ackermann function, is ≤ 4 for any n up to roughly 2^65536 — for interview and real-world purposes, treat it as O(1).

Interview Follow-ups¶

1. "Why do you need both optimizations, not just one?" — Either alone gives O(log n) amortized; together they give O(α(n)), which matters at scale but isn't strictly required to pass most interview correctness checks — mention both anyway, it signals depth.
2. "Can Union-Find tell you the size of each set?" — Yes, track size[] alongside (or instead of) rank[], updating it on every successful union.
3. "How would you support 'disconnect' operations?" — You generally can't efficiently; Union-Find is a one-way merge structure. If disconnection is required, consider an offline approach: process queries in reverse, turning deletions into unions.
4. "Union-Find vs BFS for cycle detection — when does it matter?" — For a static graph checked once, BFS/DFS is equally fine. Union-Find wins when edges arrive as a stream and you need the answer after each one, without rebuilding from scratch.

Key Takeaways¶