Union-Find (Disjoint Set Union)

What problem does Union-Find solve?#

Imagine a social network where students form friend groups. You need to answer two questions, millions of times:

• Union: Ayesha and Bilal just became friends — merge their groups.
• Find: Are Sara and Usman in the same group (connected through any chain of friends)?

A Union-Find structure — also called Disjoint Set Union (DSU) — answers both in nearly constant time. It keeps a collection of non-overlapping sets and supports:

Real uses: network connectivity, Kruskal's minimum spanning tree, detecting cycles in undirected graphs, image segmentation (connected pixels), grouping duplicate accounts, and percolation simulations.

How it works: a forest of trees#

Each set is a tree. Every element stores a pointer to its parent; the root points to itself and represents the set.

union(1, 2), union(3, 4), union(2, 4):

   1          3            1
   │    and   │    →     ┌─┴─┐
   2          4          2   3
                             │
                             4
find(2) → 1 (root)   find(4) → 3 → 1 (root)   same root ⇒ connected

A naive version can build long chains, making find O(n). Two optimisations fix that.

Optimisation 1: union by rank (or size)#

Always attach the shorter tree under the taller one, so trees stay shallow. rank is an upper bound on a tree's height.

Optimisation 2: path compression#

During find, make every node on the path point directly to the root. Future finds on those nodes take one step.

before find(5):  5 → 4 → 3 → 1 (root)       after:  5 → 1, 4 → 1, 3 → 1

With both optimisations, each operation runs in O(α(n)) amortised time, where α is the inverse Ackermann function — at most 4 for any input that fits in the universe. In practice: constant time.

Implementation#

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))       # each element starts as its own root
        self.rank = [0] * n
        self.components = n

    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, a: int, b: int) -> bool:
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False                                   # already in the same set
        if self.rank[root_a] < self.rank[root_b]:          # union by rank
            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: int, b: int) -> bool:
        return self.find(a) == self.find(b)


students = ["Ayesha", "Bilal", "Sara", "Usman", "Hina", "Omar"]
idx = {name: i for i, name in enumerate(students)}
uf = UnionFind(len(students))

for a, b in [("Ayesha", "Bilal"), ("Sara", "Usman"), ("Bilal", "Usman"), ("Hina", "Omar")]:
    uf.union(idx[a], idx[b])

print("Ayesha ~ Sara:", uf.connected(idx["Ayesha"], idx["Sara"]))
print("Ayesha ~ Omar:", uf.connected(idx["Ayesha"], idx["Omar"]))
print("friend groups:", uf.components)

Output:

Ayesha ~ Sara: True
Ayesha ~ Omar: False
friend groups: 2

Ayesha and Sara aren't direct friends, but they're connected through Bilal and Usman.

For very large inputs, Python's recursion limit can be hit in find; an iterative version walks to the root, then rewires the path in a second loop.

Classic problem: detect a cycle in an undirected graph#

Process edges one by one. If an edge connects two nodes that are already connected, adding it creates a cycle — union returns False.

def has_cycle(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return (a, b)            # this edge closes a cycle
    return None

print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))
print(has_cycle(4, [(0, 1), (1, 2), (2, 0), (2, 3)]))

Output:

None
(2, 0)

Classic problem: Kruskal's minimum spanning tree#

To connect all campuses with the cheapest total cable, sort edges by cost and add each one unless it would create a cycle. Union-Find makes the cycle check nearly O(1):

def kruskal(n, edges):
    uf, tree, total = UnionFind(n), [], 0
    for cost, a, b in sorted(edges):
        if uf.union(a, b):
            tree.append((a, b, cost))
            total += cost
    return tree, total

campuses = 5
cables = [(4, 0, 1), (8, 0, 2), (2, 1, 2), (6, 1, 3), (3, 2, 3), (9, 3, 4), (5, 2, 4)]
print(kruskal(campuses, cables))

Output:

([(1, 2, 2), (2, 3, 3), (0, 1, 4), (2, 4, 5)], 14)

Kruskal's algorithm runs in O(E log E), dominated by sorting. See the Graph Algorithms lesson for other MST and shortest-path algorithms.

Union-Find vs BFS/DFS#

Common mistakes#

• Comparing parent[a] == parent[b] instead of comparing roots via find.
• Skipping both optimisations — chains make operations O(n).
• Forgetting to map names/coordinates to indices (e.g. grid cell (r, c) → r * cols + c).
• Expecting to split sets — Union-Find only merges.

Key takeaways#

• Union-Find tracks disjoint sets with find and union.
• Union by rank + path compression give O(α(n)) — effectively constant time.
• It detects cycles in undirected graphs and powers Kruskal's MST.
• Prefer it when connections arrive incrementally and you only need "connected or not?".