15.3 Union-Find

Prerequisites: Trees and Amortized Analysis. Union-Find supports merging sets and checking connectivity without maintaining the actual paths between nodes.

The Road Between Camps Keeps Growing

The map initially contains several disconnected camps. Every time a road is built, two connected regions merge into one. The guide repeatedly asks: "Can A and B reach each other now? How many connected components remain on the map?"

If roads are only added and never removed, disjoint-set union (DSU) is well-suited for this scenario. Each set selects a representative. find(x) find the representative of an element, union(a, b) merge the trees containing the representatives of two elements; if their representatives are the same, the elements belong to the same set.

It does not tell you which specific edges are traversed. To reconstruct paths, compute shortest paths, or handle frequent edge deletions, alternative data structures or offline algorithms should be considered.

Gradually Direct Camp Signposts Toward the Central Camp

Each camp first treats itself as a representative. Once two regions are connected, simply point the root of one representative tree to the root of the other. Subsequent queries then update the signposts along the path to be progressively closer to the central camp.

class UnionFind:
    def __init__(self, size):
        if not isinstance(size, int) or isinstance(size, bool) or size < 0:
            raise ValueError("size must be a non-negative integer")
        self._parent = list(range(size))
        self._tree_size = [1] * size
        self.component_count = size

    def _check(self, element):
        if (
            not isinstance(element, int)
            or isinstance(element, bool)
            or not 0 <= element < len(self._parent)
        ):
            raise IndexError(f"element out of range: {element!r}")

    def find(self, element):
        self._check(element)
        while element != self._parent[element]:
            self._parent[element] = self._parent[self._parent[element]]
            element = self._parent[element]
        return element

    def union(self, left, right):
        left_root = self.find(left)
        right_root = self.find(right)
        if left_root == right_root:
            return False

        if self._tree_size[left_root] < self._tree_size[right_root]:
            left_root, right_root = right_root, left_root
        self._parent[right_root] = left_root
        self._tree_size[left_root] += self._tree_size[right_root]
        self.component_count -= 1
        return True

    def connected(self, left, right):
        return self.find(left) == self.find(right)

    def component_size(self, element):
        return self._tree_size[self.find(element)]


if __name__ == "__main__":
    groups = UnionFind(10)
    assert groups.union(0, 1)
    assert groups.union(1, 2)
    assert not groups.union(0, 2)
    assert groups.union(3, 4)
    assert groups.connected(0, 2)
    assert not groups.connected(0, 3)
    assert groups.union(2, 3)
    assert groups.connected(0, 4)
    assert groups.component_size(4) == 5
    assert groups.component_count == 6
    print("Union-Find check passed")

The original page invoked connected(), but the implementation lacks this method; here we complete the public contract and uniformly validate invalid indices. Duplicate merging returns False, ensuring the count of components is not reduced further.

Why Trees Don't Grow Taller Than Expected

If you arbitrarily attach one root to another, the input order can create long chains. To prevent this, we enforce a size-based merging rule: attach the root of the smaller tree directly beneath the root of the larger tree. Every time a node's tree height increases by one layer, the size of its entire set at least doubles. As a result, under this rule alone, the height of any tree remains bounded by O(log n).

find Additionally, path compression is applied: when moving toward the root, each current node is directly linked to its grandparent. This means that subsequent queries along the same path will traverse fewer nodes.

When combined with size-based (or rank-based) merging and path compression, a sequence of m operations incurs a total time complexity of O(m α(n)), where α is the inverse Ackermann function. This is an amortized bound, meaning it does not imply that each individual find operation has the same worst-case upper limit. In practice, α(n) grows extremely slowly, but in formal analysis, we must still write α(n), rather than approximating it as "always less than some constant" in the real world.

Kruskal Only Asks Whether Adding an Edge Would Create a Cycle

The guide examines roads in order of increasing cost. If the two camp sites are already part of the same connected region, adding this road would create a cycle; otherwise, the two regions are merged. The disjoint-set data structure precisely answers this question, but it does not perform the sorting of edges for Kruskal.

Kruskal’s minimum spanning tree algorithm checks edges in ascending order of weight (u, v):

• If u and v are already connected, adding this edge would form a cycle, skip it;
• Otherwise, add the edge and perform union(u, v).

The disjoint-set structure here efficiently determines whether adding an edge would create a cycle. However, the edge sorting still contributes O(E log E) time, and the disjoint-set does not reduce the entire Kruskal algorithm to O(E α(V)).

Another common application is offline dynamic connectivity. When events include deletions, they can be processed in reverse order: a forward deletion becomes an insertion in reverse. But this technique requires that all events be available offline and cannot handle all types of queries.

The Road Sign System Can't Just Loop on Its Own

Path compression frequently rewrites parent pointers, and merging by size only maintains statistics at the root. To verify the map hasn't been corrupted, you must explicitly state several invariants, never just test two camps.

At all times, the following conditions must hold:

1. The root node's parent[root] == root;
2. Every node, following its parent pointer, eventually reaches a root, without forming a cycle;
3. tree_size only has meaningful significance at the root;
4. When two distinct roots are successfully merged, the component count decreases by exactly one.

If component_count becomes too small, first verify that repeated merges still reduce the count. If a cycle appears after path compression, check that parent pointers are always updated toward ancestors. Never compare the original element's size field within union; only the root node stores the size of the set.

Hands-on Verify Union Sequences

1. Use a naive array of set labels as an oracle to verify connected.
2. Record the maximum tree height when no path compression is applied, and only union-by-size is used.
3. Replace path halving with two full passes of path compression, and compare the changes in the parent array.
4. Implement a union-find to run Kruskal's algorithm and simultaneously return the selected edges, rather than the total weight alone.
5. Explain why a standard union-find structure cannot directly delete an edge that has already been merged.

After Connected Components Are Merged

The union-find data structure discards path details, retaining only the representative element of each set. As a result, union and connectivity checks are very fast. In the next lesson, Segment Tree, a different kind of summary is preserved: the aggregated result for each interval, so that after an update, only the affected ancestors need to be recomputed.