Union-find (disjoint set union) explained: how it works, code and complexity

What problem union-find solves

Imagine a network of computers where cables are added one at a time, and after each cable you must answer "are computer A and computer B connected?". Running a graph search for every question costs O(n + m) each time. Union-find answers each question in nearly O(1) by maintaining the connected groups as cables are added.

The same need appears in Kruskal's minimum spanning tree algorithm (do these two endpoints already belong to the same tree?), in detecting cycles in an undirected graph, in grouping accounts that share an email address, in percolation simulations, and in image processing to label connected regions.

The idea in plain words

Every element points to a parent. An element that points to itself is a root, and the root is the representative of the whole group. To find the group of x, follow parent pointers until you reach a root. To merge two groups, find both roots and make one root point to the other.

Two optimizations keep the trees flat:

• Union by rank (or by size): attach the shorter (or smaller) tree under the taller (or larger) one, so the tree height grows only when two equal trees merge.
• Path compression: during find, make every node on the path point directly to the root, so the next lookup is one step.

Worked example: five elements

Start with elements 0 to 4, each in its own group. The parent array is [0, 1, 2, 3, 4]. We use union by size and make the second root the child when sizes are equal.

Python implementation

This version uses union by size and an iterative find with path compression, so it has no recursion depth problems. union returns False when the two elements were already in the same group, which is useful for cycle detection.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.groups = n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                    # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                 # ra is the larger root
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

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

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.find(3), uf.parent)       # 0 [0, 0, 0, 0, 4]
print(uf.connected(1, 4), uf.groups)  # False 2

Example: detecting a cycle in an undirected graph

Process the edges one by one. If both endpoints of an edge already have the same root, the edge closes a cycle. Kruskal's algorithm uses exactly this check after sorting edges by weight.

def has_cycle(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return True
    return False

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

Time and space complexity

α(n) is the inverse Ackermann function, which grows so slowly that it is at most 4 for any n that could fit in a real computer. In practice this means constant time per operation. Robert Tarjan proved this bound in 1975. Space is O(n) for the parent and size arrays.

Variants and common mistakes

• Comparing elements instead of roots: union must link find(a) and find(b), not a and b themselves.
• Assuming parent[x] is the representative. After unions, only find(x) is correct; call find on every element before grouping by parent.
• Recursive find on large inputs without union by rank can hit Python's recursion limit; the iterative version above avoids it.
• Elements that are not integers 0 to n-1: map them to indexes with a dict first, or store parents in a dict and add elements lazily.
• Union-find cannot split groups. If edges are deleted, you need a different structure or an offline approach that processes deletions in reverse.
• Weighted union-find stores an offset to the parent on each node, which answers questions such as "how much heavier is a than b?".

When to use it and typical problems

Use union-find when groups only ever merge and you need to ask whether two elements are in the same group, or how many groups exist. For a single connectivity question on a static graph, a plain BFS or DFS is simpler. When you need actual paths, use graph search instead, because union-find only knows membership.

Typical problems: number of connected components, number of islands (with grid cells as elements), redundant connection (the edge that creates a cycle), accounts merge, satisfiability of equality equations such as a == b, b != c, and Kruskal's minimum spanning tree.