Union-Find: Answering 'Are These Two Connected?' Almost Instantly

Quick Answer

Each set has a representative. find() returns an item's representative, union() merges two sets. Path compression and union by rank keep operations effectively O(1), which is what makes it usable on large graphs.

The problem it solves

You have items that get grouped together over time, and you repeatedly need to ask whether two items are in the same group.

Concretely: social network friend groups, cities connected by roads, pixels belonging to the same region, or accounts identified as the same person. Groups only ever merge — they never split.

A naive approach stores a list per group and searches them, which is slow as groups grow. Union-find instead gives each set a single representative, and answers "same group?" by comparing representatives.

The structure

class DSU:
    def __init__(self, n):
        self.p = list(range(n))   # each item is its own parent
        self.r = [0] * n          # rank, roughly tree height

Every item starts as its own set, being its own parent. find follows parent links upward until it reaches an item that is its own parent — the representative.

Without optimisation this degrades badly: repeated unions can build a long chain, and find then walks it every time, giving O(n). The two optimisations below are what make the structure worth using, and they are what interviewers ask about.

Path compression and union by rank

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                     # already together
        if self.r[ra] < self.r[rb]:
            ra, rb = rb, ra                  # union by rank
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1
        return True

Path compression is the line inside find. As it walks up, it points each node at its grandparent, halving the path. Repeated lookups flatten the tree, so later calls are nearly immediate.

Union by rank attaches the shorter tree under the taller one. Doing it the other way round would increase the height unnecessarily.

Together these give an amortised cost that is effectively constant for any practical input.

Using it

d = DSU(6)
for a, b in [(0,1), (1,2), (3,4)]:
    d.union(a, b)

print(d.find(0) == d.find(2))   # True  -- joined through 1
print(d.find(0) == d.find(3))   # False -- separate groups
print(d.union(0, 2))            # False -- already together

Note that 0 and 2 were never joined directly — they became connected through 1, and the structure handles that transitively without any extra work.

The False returned by union on an already-joined pair is not incidental. It is exactly the signal used for cycle detection below, so returning it rather than nothing is a deliberate design choice.

Where it appears

Cycle detection in an undirected graph. Process edges one at a time; if union returns False, both endpoints were already connected, so this edge closes a cycle. That is the whole algorithm.

Kruskal's minimum spanning tree. Sort edges by weight and add each one whose union succeeds. Union-find is what makes the cycle check fast enough for the algorithm to be practical — see greedy algorithms.

Counting connected components. Start with n components and decrement each time a union succeeds.

Grid problems — counting islands, or percolation — by treating each cell as an item and merging adjacent ones.

The limitation worth stating: union-find handles merging only. There is no efficient way to split a set, so problems involving disconnection need a different approach, usually processing the operations in reverse.

For directed graphs, cycle detection needs depth-first search with a recursion stack instead — union-find has no notion of edge direction. See topological sort.

Frequently Asked Questions