Skip to main content
Definition Website Computer and Technology

Disjoint-Set Union

Subject: Computer and Technology noun /dɪsˈdʒɔɪnt sɛt ˈjuːn.jən/ 1 definition

  1. Definition (noun)

    Entry #282 · Updated

    A 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, and Union(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 Union and flattens every visited node along a Find path 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 Find in 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 Union steps 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] = i for every rack ID and iterates over candidate fiber links sorted by millisecond latency. Before provisioning a link (42, 108) with a 1.4 ms delay, the planner verifies find(42) != find(108) in O(α(n)) amortized time to skip edges that would close a cycle, calling union(42, 108) only when the two racks belong to separate components.