Many connectivity problems need no path, only whether two items share a connected component. Image segmentation, account deduplication, and network planning may add relationships and ask that question millions of times without caring which route joins the endpoints.
Disjoint set union, also called union-find, is designed for exactly that contract. It maintains a partition of a fixed universe: every item belongs to one set, sets never overlap, and union(a, b) merges two sets. With union by size or rank and path compression, a sequence of operations takes nearly constant amortized time.
The thesis is that DSU is fast because it deliberately forgets graph detail. It stores a component representative, not edges or paths. This article derives that forest, works through connectivity, explains the amortized guarantee, and shows how offline processing and Kruskal reuse its invariant.
Model a Partition, Not the Original Graph
Let the universe contain items 0 through n - 1. At any moment, they are divided into disjoint sets whose union is the entire universe. DSU supports:
find(x): return a canonical representative of the set containingx.union(a, b): merge the sets containingaandb, reporting whether a merge occurred.connected(a, b): test whetherfind(a) === find(b).
The representative is an implementation-selected root that may change after a merge. It is not necessarily the smallest ID, earliest item, or first union argument.
Two invariants define correctness:
- Following parent links from any item eventually reaches exactly one root whose parent is itself.
- Two items are in the same set if and only if they reach the same root.
Initially, every item is its own singleton set. A successful union reduces the number of components by one; a union within one existing component changes nothing. DSU does not store which edge caused a merge, how many alternative routes exist, or the shortest route between members. Deleting an arbitrary relationship is also not supported by the basic structure because the relationship may or may not be a bridge in the original graph.
That information loss is the source of efficiency. Path reconstruction, edge deletion, or component traversal requires retaining the graph or choosing another structure. Parent pointers are balancing metadata and may connect items that were never adjacent.
Represent Sets as Parent Forests
The direct representation stores an integer parent[x] for each item. Roots point to themselves. Every other item points to another item in the same set, creating a forest of rooted trees. find follows parents to a root.
class DisjointSetUnion {
readonly #parent: number[];
readonly #size: number[];
constructor(count: number) {
this.#parent = Array.from({ length: count }, (_, index) => index);
this.#size = Array<number>(count).fill(1);
}
find(item: number): number {
let root = item;
while (this.#parent[root] !== root) root = this.#parent[root]!;
while (this.#parent[item] !== item) {
const next = this.#parent[item]!;
this.#parent[item] = root;
item = next;
}
return root;
}
union(left: number, right: number): boolean {
let leftRoot = this.find(left);
let rightRoot = this.find(right);
if (leftRoot === rightRoot) return false;
if (this.#size[leftRoot]! < this.#size[rightRoot]!) {
[leftRoot, rightRoot] = [rightRoot, leftRoot];
}
this.#parent[rightRoot] = leftRoot;
this.#size[leftRoot] = this.#size[leftRoot]! + this.#size[rightRoot]!;
return true;
}
}
The first find loop discovers the root; the second compresses the visited path to that root. This iterative form avoids call-stack depth concerns. A production wrapper should validate indices and can track component count by decrementing it only when union returns true.
Only root entries in size are authoritative. Values left under non-roots may be stale and must not be read as component sizes. That convention avoids updating every member during a merge, which would destroy the performance advantage.
Keep Trees Shallow with Weighted Union
A naive union(a, b) could always attach the root of b under the root of a. An unfortunate sequence then builds a chain. If unions attach 0 under 1, then that root under 2, and so on, finding 0 takes linear time before compression.
Union by size prevents that shape. Compare the number of members represented by each root and attach the smaller tree under the larger. When a node’s depth increases by one, the size of its new tree is at least twice the size of its old tree. A set cannot double more than floor(log2(n)) times, so tree height is at most even without path compression.
Union by rank is a close alternative. Rank is an upper bound on tree height. Attach lower rank under higher rank; when equal ranks merge, choose one root and increment its rank. Path compression later makes actual heights smaller, but ranks are not reduced. They remain balancing metadata, not a live height measurement.
Size directly provides component cardinality; rank may fit more compactly. Combining both adds no useful guarantee: choose one and update it only at roots.
Argument order should not control balance. Merge component metadata such as total weight or bounding box at the chosen root with the parent update. A deterministic equal-size tie rule improves reproducibility without changing asymptotic cost.
Metadata needs its own merge law. Counts and sums combine naturally, while labels, owners, or representative records need an explicit conflict rule. Update metadata only after both roots are known and only on a successful union; otherwise a redundant edge can be counted twice. If metadata merge can fail, compute its result before changing parents so the partition and payload cannot diverge halfway through an operation.
Compress Paths Without Changing Components
Path compression rewrites parent pointers during find so future operations reach the root faster. It is safe because every rewritten pointer stays within the same component and points to its existing representative. The partition does not change; only the forest shape does.
Full compression makes every visited node a root child. Path splitting points each node to its grandparent; path halving updates every other node. All pair with weighted union and provide practical near-constant amortized behavior with different write patterns.
Compression has consequences beyond speed. A read-like find mutates the structure, so it is not safe to run concurrently with other operations without synchronization. It also makes rollback difficult because one query can rewrite many pointers. Algorithms that need snapshots or undo commonly disable full compression and use union by size with an explicit change log.
Do not cache representatives externally: a later union can make a former root a child. A representative is stable only until the next relevant merge unless the DSU is frozen.
Compression is also not a substitute for weighted union. Compression makes frequently queried paths flat, but a long chain can still be constructed among untouched nodes. Conversely, weighted union alone gives logarithmic worst-case operations, which is already robust but not as fast over long mixed sequences. The standard performance claim assumes both heuristics.
Work Through an Incremental Connectivity Example
Imagine seven network sites labeled 0 through 6. Links arrive in this order:
(0, 1), (1, 2), (3, 4), (5, 6), (2, 4), (0, 4)
Initially there are seven components. Union (0, 1) creates {0, 1} and reduces the count to six. Union (1, 2) first finds the root of 1, then attaches singleton 2 to the size-two component, producing {0, 1, 2}. Separately, (3, 4) and (5, 6) create two size-two components.
Before the fifth link, connected(0, 4) is false because the roots differ. Union (2, 4) merges the size-three component containing 2 with the size-two component containing 4. The exact root depends on tie and argument history, but the logical component is {0, 1, 2, 3, 4} and its stored root size must be five. The component count is now two.
The final link (0, 4) is redundant. Both endpoints already find the same root, so union returns false and the component count remains two. That boolean is valuable: it distinguishes a relationship that joins components from one that creates a cycle in the accumulated undirected graph.
If a parent path is 3 -> 4 -> 0, find(3) returns 0 and compression points visited nodes toward 0. Later checks inspect fewer cells; the new parent pointer still does not claim a direct network link.
This example supports an online stream of additions and queries. After every link, the service can report component count, whether the link merged components, and component size. It cannot correctly process removal of (2, 4) by separating the DSU tree: other original links may still connect the two sides, and path compression has erased any correspondence between parent edges and network edges.
Explain the Near-Constant Amortized Bound
With weighted union but no compression, an operation follows at most logarithmic tree height. With path compression as well, a sequence of operations on items takes
under the standard analysis, where is the inverse Ackermann function. For any data set that can exist in an actual machine, is less than a small constant. This is why DSU is commonly described as nearly constant time.
The word amortized is essential. One find can still walk a nontrivial path. The guarantee averages work across the sequence: expensive traversals flatten paths and make later traversals cheaper. It is not correct to claim a strict worst-case latency for every call.
The proof groups nodes by growing rank levels and charges traversals to future compression. Practically, weighted union makes depth increase only after substantial component growth, then compression removes repeated traversal of that depth.
Input validation and map lookup can dominate this theoretical cost. If domain keys are strings, a wrapper usually maps them to dense integer IDs; hashing those strings is outside the DSU bound. Component metadata merges may also be expensive. State complexity honestly: the parent-forest operations are near constant amortized, while total application cost includes key mapping and any payload aggregation.
The inverse-Ackermann bound assumes a sequence over a fixed indexed universe and the standard balancing and compression rules. Creating IDs, resizing backing arrays, synchronization, or persisting snapshots adds separate costs. Even so, DSU is attractive because its core memory is linear: one parent and one size or rank value per item, plus optional root metadata.
Use Offline Order to Recover More Connectivity Cases
Basic DSU accepts additions but not arbitrary deletions. Offline processing can sometimes reverse time so deletions become additions. Suppose a complete sequence of edge removals and connectivity queries is known in advance. Start from the graph after all removals, build a DSU from edges that remain, then scan operations backward. A forward removal becomes a backward addition, which union handles naturally. Record each query answer while scanning and reverse the answer list at the end.
This technique requires careful multiplicity accounting. If the same undirected edge is added twice and removed once, one copy remains active. Normalize endpoint order and count active copies rather than treating edges as a simple set. Queries at the same logical timestamp need a defined before-or-after mutation convention.
For example, if forward operations are remove(1, 2), then connected(1, 3), the reverse scan must answer the query before adding (1, 2) back. Reversing list order alone handles that convention; regrouping operations by timestamp may not. Write the temporal rule next to the input model and test adjacent mutation-query pairs in both orders.
General offline dynamic connectivity assigns each edge’s active interval to a segment tree over time, traverses it, and rolls back unions when leaving a segment. Rollback records changed parents, sizes, and component count. It normally omits compression so each union changes bounded state; union by size retains logarithmic depth.
Offline techniques trade immediacy and implementation simplicity for capability. They are appropriate for batch audit logs, simulation, and historical analysis where the full operation sequence is available. They do not make a basic DSU support unpredictable live deletions. For an online system, buffering all queries until tomorrow may violate the product contract even if the batch algorithm is elegant.
Integrate DSU with Kruskal’s Algorithm
Kruskal’s minimum spanning forest algorithm is a direct consumer of the same component invariant. Sort undirected weighted edges by nondecreasing weight. Begin with singleton vertices. For each edge (u, v, weight), call union(u, v). If it returns true, accept the edge; it connects two previously separate components. If it returns false, reject the edge because its endpoints already have a route through accepted edges, so adding it would create a cycle.
For a connected graph, stop after accepting vertexCount - 1 edges. For a disconnected graph, the result is a minimum spanning forest. Sorting costs for E edges and dominates the near-constant DSU operations. Stable sorting is not required for total weight correctness, but deterministic tie-breaking by normalized endpoints makes the exact chosen forest reproducible when several minimum solutions exist.
sort edges by (weight, normalized endpoints)
for each edge (u, v):
if union(u, v) succeeds: accept the edge
DSU’s role here is narrow: answer whether accepting one edge would join components. It does not prove the greedy choice by itself, perform sorting, reconstruct arbitrary paths, or support directed spanning structures. Keeping that boundary clear prevents a useful component data structure from being mistaken for a complete graph toolkit.
Test Invariants, Boundaries, and Workload Behavior
Example tests should cover zero and one item, repeated union, self-union, two independent components, merges of unequal and equal sizes, invalid indices, component count, and component size. The seven-site worked example should finish with two components, size five for every member 0 through 4, size two for 5 and 6, and union(0, 4) === false.
Property-based testing can maintain a slow reference partition. For small universes, store a component label for every item and relabel all members on union. Generate random unions and queries, then compare connectivity, sizes, and component count after each step. This oracle is inefficient but simple enough to trust.
White-box assertions can verify that every parent is in range, every parent chain reaches a self-parent without a cycle, root sizes sum to the universe size, and recorded component count equals the number of roots. After calling find(x) under full compression, parent[x] should be the returned root. Do not require a particular representative unless deterministic roots are part of the contract.
For offline reverse processing, test duplicate edges, removal of a missing edge, queries before and after mutation, and empty final graphs. For rollback, snapshot the change-log length before entering a time segment and prove that rollback restores parent arrays, sizes, and component count exactly. Kruskal integration tests should compare total weight against brute-force spanning choices on tiny graphs and include disconnected vertices and equal-weight ties.
At scale, measure item and component counts, successful versus redundant unions, key-map memory, and sampled parent traversals. Rising traversal length can reveal a path bypassing weighting or compression. Because compression writes during queries, concurrent access needs exclusive ownership, locking, or a purpose-built implementation.
DSU earns its performance by answering one question and discarding the rest. Parent forests encode set membership, weighted union limits depth, and path compression turns earlier traversal into future savings. Offline ordering expands the class of workloads when time can be rearranged, while Kruskal uses successful unions as cycle-free edge decisions. With the partition invariant and information boundary explicit, near-constant connectivity is not a trick; it is the result of storing exactly what the query requires and no more.