15.3 Union-Find

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

Edges Keep Arriving

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) finds the representative of an element, union(a, b) merges 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.

Shorten the Path to the Root

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):
        self._check(left)
        self._check(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):
        self._check(left)
        self._check(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")

Element indices are fixed at 0..size-1; elements cannot be added later. An empty structure has zero components and no valid element to query. The constructor rejects negative values, non-integers, and booleans; methods raise IndexError for invalid indices. Both arguments are checked before either lookup, so an invalid right argument cannot first modify the left path. Repeated unions return False without reducing the component count. find and connected also mutate parent pointers and are not side-effect-free concurrent reads.

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. Whenever a node gains one level of depth because its smaller tree is attached to a larger tree, its set size at least doubles. As a result, under this rule alone, the height of any tree remains bounded by O(log n).

find applies path halving: when moving toward the root, each current node is directly linked to its grandparent. Later queries along that path will generally traverse fewer nodes. A root identifies the set; it need not be the smallest element, and later unions can change it.

When combined with size-based (or rank-based) merging and path compression, initializing n elements costs Θ(n), followed by O(m α(n)) total time for m operations, giving O(n+m α(n)) overall, 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. A single lookup still has an O(log(n+1)) worst-case bound, and storage is Θ(n). Princeton’s path-halving implementation also distinguishes initialization, individual operations, and amortized sequences. α(n) grows slowly, but a fixed constant without a size range does not define it.

Kruskal Only Asks Whether Adding an Edge Would Create a Cycle

For an undirected weighted graph, Kruskal checks edges (u, v) in ascending weight order. A connected graph yields a minimum spanning tree; a disconnected graph yields a minimum spanning forest:

• 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. Sorting still costs O(E log(E+1)). Including initialization of V vertices, the usual implementation takes O(V+E log(E+1)+E α(V)) time. Union-find neither answers directed reachability nor removes the sorting cost.

Another common application is offline dynamic connectivity. If events consist only of edge deletions and connectivity queries, first build the final graph, then reverse the sequence so deletions become insertions. If forward events also add edges, reverse processing encounters deletions again; ordinary union-find is insufficient. Further offline decomposition and rollback union-find are common tools for that case. These methods require access to the complete event sequence.

Parent Pointers Must Form a Forest

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, check whether repeated merges incorrectly 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.

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.