Disjoint set union (DSU), also called union-find, is a data structure that maintains a partition into non-overlapping sets. It can merge two sets and tell whether two items belong to the same set. For a stream of newly observed links in an undirected counterparty graph, it can answer whether two institutions are connected through any chain of links observed so far.
Initially, each item is in its own set. In a parent-pointer implementation, each set is a tree whose root points to itself.
find(x)follows parent pointers fromxto its root. Two items belong to the same set exactly when their roots match.union(x, y)finds both roots. If they differ, it makes one root a child of the other. If they already match, the partition stays the same.
Union by size attaches the root of the smaller set under the root of the larger one. Path compression makes every node visited by a find point straight to the root once the root is known. The root serves as a representative and can change after a later merge. Tarjan’s set-union report
One lookup shortens the next
Start with six fictional institutions numbered 0 through 5. Process the undirected links in order with
union(0, 1), union(2, 3), union(0, 2) and union(4, 5). Use union by size and let the smaller root ID win a tie.The first two unions form pairs rooted at 0 and 2. The third attaches root 2 to root 0. Node 3 still points to 2, so its first lookup follows . During that lookup, path compression changes the parent of 3 to 0. The next lookup takes one hop instead of two. The two sets still have roots 0 and 4 and sizes 4 and 2.
The first find(3) rewires the parent pointer of node 3. Its root and both components stay the same.
What the time bound counts
With union by size alone, the depth of an item increases only when its set is attached under another set at least as large. Its set size at least doubles each time, so a find takes at most time. Path compression makes later lookups cheaper by shortening paths that have already been traversed.
Using both rules, a one-argument bound for find and union calls on preallocated elements is , plus to initialise the singleton sets. Here is an inverse Ackermann function. It grows extremely slowly, and sharper formulations use a two-argument variant that also depends on the number of calls. The bound is amortised over the sequence. An individual find can still traverse a logarithmic-depth path. Sedgewick and Wayne on the amortised bound
When an edge disappears
Parent pointers record membership. They can point between institutions that never had a direct link. In the example, deleting the input edge would split the first component into and . If had also arrived before the deletion, the first component would stay connected, even though adding that extra link had left the partition unchanged. The same partition before deletion can therefore require two different answers afterwards. A plain DSU supports edge additions. A graph with expiring edges needs to recompute connectivity from the remaining edges or maintain it with a structure that handles deletions. Pătrașcu and Thorup on incremental and fully dynamic connectivity
Kruskal’s minimum spanning tree algorithm fits the insertion-only case. It considers edges in increasing weight order. If the endpoints already share a root, the candidate edge would close a cycle, so Kruskal skips it. Otherwise it accepts the edge and merges the components. The accepted edges are stored separately from the parent pointers. Sedgewick and Wayne on Kruskal’s cycle check
The SelfMadeQuant lesson traces the rank-based version and has worked exercises on the same operations. The public preview is open and the full lesson requires membership. Union-Find with Union by Rank and Path Compression
Sources
- Robert E. Tarjan (1974). Efficiency of a Good But Not Linear Set Union Algorithm.
- Robert Sedgewick and Kevin Wayne. Union-Find and Minimum Spanning Trees, lecture slides for Algorithms, fourth edition.
- Mihai Pătrașcu and Mikkel Thorup (2011). Don’t Rush into a Union: Take Time to Find Your Roots.