Union-Find (Disjoint Set Union) Explained

Two operations on a partition

Initially, every element belongs to its own set. find(x) returns the representative of the set containing x; two elements are connected exactly when their representatives match. union(a, b) combines the sets containing those elements.

A naive forest can become a long chain. Two optimizations keep it shallow: path compression rewires nodes visited during find directly toward the root, while union by size attaches the smaller tree under the larger one. With both, each operation takes amortized O(α(n)) time, where the inverse Ackermann function grows so slowly that it is effectively constant for practical input sizes.

Python implementation

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

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        return True

The return value indicates whether two different components were merged. That detail is useful in Kruskal's minimum spanning tree algorithm: an edge is accepted only when union joins previously separate components.

Where it shines—and where it does not

Use Union-Find for dynamic connectivity under edge additions, counting connected components, cycle checks in undirected graphs, and grouping equivalent items. It is especially useful when the input is a stream of “connect these two” operations and queries ask whether pairs are now connected.

It does not naturally support removing edges, reporting an actual path between two nodes, or maintaining arbitrary graph structure. For those operations, use a graph representation and suitable traversal or dynamic graph algorithm. Also, Union-Find groups are not inherently ordered; roots are implementation details, not stable labels.