Union-Find (Disjoint Set)

Union-Find, also called a Disjoint Set Union (DSU), is a data structure that keeps a collection of elements partitioned into disjoint (non-overlapping) sets and answers two questions extremely fast: are two elements in the same set, and merge two sets into one. It shows up constantly in graph problems — detecting cycles in an undirected graph, building Kruskal’s minimum spanning tree, counting connected components, and grouping items by connectivity (accounts that share an email, cities linked by roads). What makes it remarkable is that with two small optimizations it turns operations that look like they should cost O(n) into operations that run in almost constant time.

Overview: How It Works

Picture six people at a new company, numbered 0 through 5, none of whom know each other yet. Each person starts as their own one-person "team." Whenever two people are introduced, their teams merge into one. At any point you might want to ask: are person A and person B on the same team? Union-Find is built exactly for this scenario: a changing collection of groups, where you need fast merge and fast same-group? operations.

Internally, each set is represented as a tree, not by listing its members. Every element has a parent pointer; the element whose parent points to itself is the root, and the root serves as the set’s representative. find(x) walks parent pointers upward until it reaches a root, and two elements are in the same set exactly when find(x) == find(y). union(x, y) merges two sets by finding both roots and attaching one root under the other — a single pointer change, regardless of how many elements are in either set.

Implemented naively, this works but can degrade badly. If you always attach the second tree under the first without any care, repeatedly unioning elements in increasing order (0 with 1, 1 with 2, 2 with 3, …) produces one long chain, so find on the far end takes O(n) steps — no better than a linked list. Two optimizations fix this:

Union by Rank / Union by Size

Instead of arbitrarily deciding which root becomes the new parent, always attach the smaller or shallower tree under the root of the larger or deeper tree. This keeps the resulting tree from growing deeper than necessary — a tree’s depth can only increase when two trees of equal rank merge, and each such merge at least doubles the size, so depth stays O(log n).

Path Compression

While walking up during find(x), make every node visited point directly at the root instead of at its old parent. The next time any of those nodes calls find, the walk is one hop instead of many. Applied repeatedly, path compression flattens the trees over time.

Used together, union by rank/size and path compression give an amortized time of O(α(n)) per operation, where α is the inverse Ackermann function. It grows so slowly that α(n) is at most 4 for any input size that could ever exist in practice — which is why people casually call Union-Find operations "O(1)."

Time and Space Complexity

Version	find(x)	union(x, y)
No optimizations	O(n) worst case	O(n) worst case
Union by rank/size only	O(log n)	O(log n)
Path compression only	O(log n) amortized	O(log n) amortized
Both (standard Union-Find)	O(α(n)) amortized	O(α(n)) amortized

The reasoning: without union by rank, a sequence of unions in increasing order builds a straight chain of depth n, so a single find at the far end costs O(n). Union by rank bounds tree depth to O(log n) because depth can only grow when merging equal-rank trees, and each such merge at least doubles the affected subtree’s size — you can only double a quantity log n times before exceeding n. Path compression then flattens trees as a side effect of every find call, so later calls on the same elements become O(1). Combining both, a careful amortized analysis (the potential-function argument that gives rise to the inverse Ackermann function) shows that any sequence of m operations on n elements costs O(m · α(n)) total. Space is O(n): one integer per element for the parent array, plus another O(n) array if you track rank or size.

Examples

Example 1: A Union-Find Class With Path Compression and Union by Rank

class UnionFind:
    def __init__(self, size: int) -> None:
        self.parent = list(range(size))
        self.rank = [0] * size

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

    def union(self, x: int, y: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True


def main() -> None:
    uf = UnionFind(6)
    edges = [(0, 1), (1, 2), (3, 4)]
    for a, b in edges:
        uf.union(a, b)

    print(uf.find(0) == uf.find(2))
    print(uf.find(0) == uf.find(3))
    print(uf.find(3) == uf.find(4))

    uf.union(2, 3)
    print(uf.find(0) == uf.find(4))


main()

Output:

True
False
True
True

After the first loop, unions (0,1), (1,2) and (3,4) merge 0/1/2 into one set and 3/4 into another, so find(0) == find(2) is True but find(0) == find(3) is False, and 3/4 are together. The explicit uf.union(2, 3) then merges the two remaining sets, so find(0) == find(4) becomes True — and because find recurses with path compression, every node touched along the way (including 4) ends up pointing straight at the final root.

Example 2: Counting Connected Components

def count_components(n: int, edges: list[tuple[int, int]]) -> int:
    parent = list(range(n))
    size = [1] * n

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving
            x = parent[x]
        return x

    def union(x: int, y: int) -> None:
        root_x, root_y = find(x), find(y)
        if root_x == root_y:
            return
        if size[root_x] < size[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_y] = root_x
        size[root_x] += size[root_y]

    components = n
    for a, b in edges:
        if find(a) != find(b):
            union(a, b)
            components -= 1

    return components


def main() -> None:
    n = 5
    edges = [(0, 1), (1, 2), (3, 4)]
    print(count_components(n, edges))


main()

Output:

2

This version uses union by size instead of rank (a common variant with identical complexity) and path halving: instead of a recursive call, find repeatedly repoints each node at its grandparent while walking up, which flattens the tree iteratively without recursion. Starting from 5 singleton components, edges (0,1) and (1,2) merge nodes 0, 1 and 2 into one component (2 merges, each shrinking the count by one), and edge (3,4) merges another pair. Node 4 (index 4, since n=5 means nodes 0–4) was already covered by the (3,4) merge, leaving two components total: {0,1,2} and {3,4}.

Example 3: Cycle Detection in an Undirected Graph

def has_cycle(n: int, edges: list[tuple[int, int]]) -> bool:
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for a, b in edges:
        root_a, root_b = find(a), find(b)
        if root_a == root_b:
            return True
        parent[root_b] = root_a

    return False


def main() -> None:
    n = 4
    edges_without_cycle = [(0, 1), (1, 2), (2, 3)]
    edges_with_cycle = [(0, 1), (1, 2), (2, 0)]

    print(has_cycle(n, edges_without_cycle))
    print(has_cycle(n, edges_with_cycle))


main()

Output:

False
True

This is the classic Union-Find cycle check: for each edge, if both endpoints already share a root, the edge would connect two nodes that are already connected — that’s a cycle, so we return True immediately without adding the edge. The first edge list forms a simple path 0–1–2–3 with no repeats, so every edge connects two different components and the function returns False. The second list adds edge (2, 0) after (0,1) and (1,2) already connected 0, 1 and 2 into one set, so find(2) == find(0) and the function reports a cycle.

How It Works Step by Step

Trace Example 1’s calls on parent = [0, 1, 2, 3, 4, 5], rank = [0, 0, 0, 0, 0, 0]:

Step	Call	parent after	What happened
1	union(0, 1)	[0, 0, 2, 3, 4, 5]	Equal ranks: 1 attaches under 0, rank[0] becomes 1
2	union(1, 2)	[0, 0, 0, 3, 4, 5]	find(1) compresses straight to 0; 2 attaches under 0 (lower rank)
3	union(3, 4)	[0, 0, 0, 3, 3, 5]	Equal ranks: 4 attaches under 3, rank[3] becomes 1
4	union(2, 3)	[0, 0, 0, 0, 3, 5]	Equal ranks (both 1): 3 attaches under 0, rank[0] becomes 2
5	find(4)	[0, 0, 0, 0, 0, 5]	Walks 4 → 3 → 0; path compression repoints both 3 and 4 straight at root 0

Step 5 is the payoff: before path compression, reaching 4’s root took two hops (4 → 3 → 0); after that single find call, parent[4] points directly at 0, so every future find(4) is one hop. This is exactly why a long sequence of finds on the same structure gets faster over time.

Common Mistakes

Mistake 1: Comparing Elements Instead of Their Roots

A very common bug is skipping find() entirely and comparing (or linking) raw elements instead of their set representatives:

def union_wrong(parent: list[int], x: int, y: int) -> None:
    if x != y:  # BUG: compares raw elements, not their set representatives
        parent[x] = y  # BUG: overwrites x's parent even when x already has children


parent = [0, 1, 2, 3]
union_wrong(parent, 0, 1)
union_wrong(parent, 1, 2)
union_wrong(parent, 0, 2)
print(parent)

Output:

[2, 2, 2, 3]

This happens to produce a plausible-looking array for a tiny example, but it’s broken: it never checks whether x and y are already connected (so it can’t detect a cycle), and it overwrites parent[x] directly instead of the root’s parent — if x already had other elements pointing to it, those children silently become disconnected from the rest of their set. Always resolve both sides to their roots with find() before comparing or linking.

def find(parent: list[int], x: int) -> int:
    while parent[x] != x:
        x = parent[x]
    return x


def union_correct(parent: list[int], x: int, y: int) -> bool:
    root_x, root_y = find(parent, x), find(parent, y)
    if root_x == root_y:
        return False  # x and y are already connected
    parent[root_x] = root_y
    return True


def main() -> None:
    parent = [0, 1, 2, 3]
    print(union_correct(parent, 0, 1))
    print(union_correct(parent, 1, 2))
    print(union_correct(parent, 0, 2))  # 0 and 2 are already connected through 1


main()

Output:

True
True
False

Now the third call correctly reports False: by the time it runs, 0 and 2 are already in the same set (connected through 1), so union_correct refuses to merge again — exactly the signal you need for cycle detection.

Mistake 2: Skipping Union by Rank/Size, Getting a Degenerate Chain

Even with a working find() and union(), always attaching one root under the other without comparing tree sizes lets a bad input order build a straight chain:

def find_naive(parent: list[int], x: int) -> int:
    while parent[x] != x:
        x = parent[x]
    return x


def union_naive(parent: list[int], x: int, y: int) -> None:
    root_x = find_naive(parent, x)
    root_y = find_naive(parent, y)
    if root_x != root_y:
        parent[root_x] = root_y  # always attach x's root under y's root, ignoring size


parent = list(range(6))
for i in range(5):
    union_naive(parent, i, i + 1)  # builds a straight chain: 0 -> 1 -> 2 -> 3 -> 4 -> 5

print(parent)

Output:

[1, 2, 3, 4, 5, 5]

The array looks harmless, but it encodes a chain: node 0’s parent is 1, whose parent is 2, and so on up to root 5. find_naive(0) must take five hops to reach the root. With no path compression and no union by rank, a sequence of n such unions makes the next find cost O(n) instead of the near-constant time Union-Find is known for — there’s nothing rebalancing the tree as it grows. Fix it by comparing rank (or size) before attaching, and by compressing paths during find:

def find_compressed(parent: list[int], x: int) -> int:
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:  # path compression: point every node on the path directly at the root
        parent[x], x = root, parent[x]
    return root


def union_by_rank(parent: list[int], rank: list[int], x: int, y: int) -> None:
    root_x, root_y = find_compressed(parent, x), find_compressed(parent, y)
    if root_x == root_y:
        return
    if rank[root_x] < rank[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_y] = root_x
    if rank[root_x] == rank[root_y]:
        rank[root_x] += 1

Here find_compressed makes two passes: the first walks to the true root without modifying anything, and the second re-walks the same path, repointing every node directly at that root. Combined with the rank check in union_by_rank, no single sequence of operations can force the tree deeper than O(log n), let alone into a chain.

Best Practices

• Always implement both path compression and union by rank/size together — either one alone leaves you at O(log n), not the near-constant O(α(n)) you get from combining them.
• Reach for Union-Find when you only need connectivity queries (same set or not) and merges. If you need the actual path between two nodes, or shortest distance, use BFS/DFS or Dijkstra instead — Union-Find throws away path information on purpose.
• When elements aren’t already small integers (strings, tuples, email addresses), map them to indices with a dict first; Union-Find’s speed comes from being array-based.
• For Kruskal’s minimum spanning tree: sort edges by weight, then use Union-Find to skip any edge whose endpoints are already connected (it would form a cycle).
• Have union() return a bool indicating whether a merge actually happened. False means the elements were already in the same set — a cycle indicator you get for free.
• Track the number of remaining components as a counter you decrement on every successful union, so "how many groups are left" is an O(1) query instead of a full scan.
• On very large inputs, prefer an iterative, while-loop-based find (as in Examples 2 and 3) over a recursive one (as in Example 1) to avoid brushing against Python’s recursion limit.

Practice Exercises

1. Number of Provinces. Given an n x n adjacency matrix is_connected where is_connected[i][j] == 1 means cities i and j are directly connected, return the number of provinces (groups of cities connected directly or indirectly). Hint: union every pair (i, j) where is_connected[i][j] == 1, then count how many distinct roots remain among all n cities.

2. Redundant Connection. You’re given the edges of a graph that started as a tree on n nodes and then had exactly one extra edge added, creating a single cycle. Find that extra edge. Hint: process edges in order and union each pair; the first edge whose two endpoints are already connected before you add it is the answer.

3. Accounts Merge. Given a list of accounts, each with a name and a list of emails, merge accounts that share at least one email — they belong to the same person. Hint: map every distinct email to an integer index with a dict, union all emails that appear together in one account, then group email indices by their root to rebuild the merged accounts.

Summary

• Union-Find (Disjoint Set Union) maintains a collection of disjoint sets and supports two operations: find(x) (which set is x in?) and union(x, y) (merge two sets).
• Sets are represented as trees; the root of a tree is the set’s representative, and find(x) == find(y) tests whether x and y are in the same set.
• Without optimization, Union-Find can degrade to O(n) per operation on a chain-shaped tree.
• Union by rank/size (attach the smaller tree under the larger) plus path compression (flatten the path during every find) bring the amortized cost down to O(α(n)) — effectively constant time.
• Space cost is O(n) for the parent array, plus O(n) more if you track rank or size.
• Classic uses: cycle detection in undirected graphs, counting connected components, Kruskal’s minimum spanning tree, and grouping related items (accounts, provinces, friend circles).
• Always compare find(x) == find(y), never x == y directly, when checking connectivity.