Disjoint-set union (union-find)

The structure partitions objects into disjoint sets. Find obtains a representative, union merges sets, and comparing representatives tests whether two objects currently share a group.

Adding edges to an undirected graph can merge the endpoints’ connected components. Connectivity is reflexive, symmetric, and transitive. Directed reachability need not be symmetric and therefore is not represented by simply applying the same merging rule.

References: [1]

A forest implementation stores a parent link for each object. Following links reaches a self-parented root. Union first finds both roots and links one to the other, preserving component membership.

Weighted merging attaches the smaller tree to the larger, limiting depth. Path compression makes examined nodes point more directly toward the root, reducing later traversals. Because representatives can change during union, they are not permanent application identity names.

References: [1]

Weighted merging alone gives a logarithmic depth bound, and compression improves repeated lookup work. Bounds must match the actual merging and compression policy rather than assuming that every implementation performs constant work on every call.

Basic union-find does not automatically split a component after deleting an edge, nor does it retain a complete route between objects. Edge deletion, historical rollback, and path recovery require additional structures or algorithms designed for those tasks.

References: [1]