Disjoint-Set Union
Subject: Computer and Technology noun /dɪsˈdʒɔɪnt sɛt ˈjuːn.jən/ 1 definition
- computer-science
- data-structures
- graph-algorithms
- algorithm-design
-
Definition (noun)
Entry #282 · UpdatedA Disjoint-Set Union (DSU), also known as a union-find structure, is a specialized data structure that maintains a dynamic partition of elements grouped into non-overlapping, or disjoint, subsets. Each subset is represented internally as a rooted tree stored inside a flat parent-pointer array, where one distinguished root node serves as the canonical representative for all members of its set. Initialized from singleton sets via
MakeSet, the structure supports two primary operations—Find(x), which follows parent pointers to locate an element's root representative, andUnion(x, y), which merges two subsets by linking one root beneath the other—achieving an amortized time complexity of O(α(n)) per operation (where α is the extremely slow-growing inverse Ackermann function) when paired with path compression and rank- or size-based merging. Because DSU tracks only equivalence-class membership and supports merging rather than splitting sets or traversing intra-component edges, it excels at incremental connectivity checks, cycle detection, and Kruskal's minimum spanning tree algorithm, whereas workloads requiring arbitrary edge deletions or set splits need richer dynamic graph structures.Common Forms
Rank-Compressed Disjoint-Set Forest: Attaches the root with lower tree height (rank) beneath the taller root during
Unionand flattens every visited node along aFindpath directly to the root, guaranteeing the canonical O(α(n)) amortized bound.Size-Weighted Disjoint-Set Forest: Merges smaller subsets into larger ones by tracking exact element counts—often stored as negative integers inside each root's parent-array slot—allowing O(1) component-size queries alongside near-constant-time operations.
Iterative Path-Splitting and Path-Halving Variants: Optimize
Findin a single traversal by relinking either every visited node (splitting) or every other node (halving) to its grandparent, preserving O(α(n)) amortized complexity without recursion stack overhead or a second pass.Rollback Disjoint-Set Union: Omits path compression while retaining union by rank or size and logs parent-array mutations onto an undo stack, enabling
Unionsteps to be reverted in reverse order for offline dynamic connectivity at O(log n) worst-case time per operation.
Example
When a cloud networking tool computes a minimum-latency, loop-free backbone across 10,000 server racks using Kruskal's algorithm, it initializes a DSU structure with
parent[i] = ifor every rack ID and iterates over candidate fiber links sorted by millisecond latency. Before provisioning a link(42, 108)with a1.4 msdelay, the planner verifiesfind(42) != find(108)in O(α(n)) amortized time to skip edges that would close a cycle, callingunion(42, 108)only when the two racks belong to separate components.