Union-Find

#How does it work?

Union-Find (disjoint set union) splits elements into non-overlapping sets and answers two questions very quickly: merge two sets, and are two elements in the same set?

Each set is stored as a tree; every element only knows its parent, and the root is the set's representative. The whole structure fits in one parent array.

Two improvements keep the trees almost flat: union by rank hangs the shorter tree under the taller one, and path compression points every node visited by find straight at the root.

#Try it yourself

#Basic operations

find(x)

Follows parents to the root (representative) of x and shortens the path with path compression.

union(a, b)

Finds the roots of a and b; if they differ, links the lower-rank root under the other.

connected(a, b)

Two elements are in the same set when find(a) == find(b).

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

class UnionFind:
    def __init__(self, n: int) -> None:
        self._parent = list(range(n))  # every element is its own root
        self._rank = [0] * n  # an upper bound on each tree's height
        self.sets = 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) -> None:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return  # already in the same set
        # Union by rank: hang the shorter tree under the taller one.
        if self._rank[ra] < self._rank[rb]:
            ra, rb = rb, ra
        self._parent[rb] = ra
        if self._rank[ra] == self._rank[rb]:
            self._rank[ra] += 1
        self.sets -= 1

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)


uf = UnionFind(8)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
uf.union(5, 6)
show = lambda b: "true" if b else "false"
print(show(uf.connected(0, 2)))  # true
print(show(uf.connected(0, 5)))  # false
print(uf.sets)                   # 4: {0,1,2,3} {4} {5,6} {7}

#Complexity

α(n) is the inverse Ackermann function; it stays below 5 even for as many elements as there are atoms in the universe. With both improvements the operations are constant time in practice. Without them a tree can degrade into a chain and find becomes O(n).

#When to use it?

Kruskal's minimum spanning tree, counting connected components, cycle detection in undirected graphs, network connectivity questions and region labelling in image processing use union-find.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Kruskal's Algorithm