Skip to content

Disjoint-Set Data Structure

Maintain a mutable partition under Make-Set, Find, and Union, typically with representative-rooted forests, union by rank or size, and path compression for inverse-Ackermann amortized time.

Version
v3 · 2026-09-19 · History
Domain-specific #
1691
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomain
Data Structures → Computer Science & Software Engineering
Aliases
Union–find, Union-find data structure, Merge–find set, Disjoint-set union, DSU

Core Idea

A disjoint-set data structure maintains a partition of elements into pairwise-disjoint sets. Make-Set(x) creates a singleton, Find(x) returns a representative of the unique block containing \(x\), and Union(x,y) merges the two blocks when distinct. The standard disjoint-set forest represents each block as a rooted tree; union by rank/size limits height and path compression rewires search paths toward the root.[1]

The recognition invariant is mutable partition + stable representative equivalence test + union-only coarsening + forest heuristics + amortized efficiency.

How would you explain it like I'm…

Team Captains

Imagine kids split into teams, and each team has a captain. To check if two kids are on the same team, you ask each one, 'Who's your captain?' To join two teams, one captain agrees to follow the other captain. The disjoint-set data structure keeps track of teams like this, with tricks so that finding your captain stays quick.

Who's Your Group Leader?

A disjoint-set data structure keeps track of items split into groups, where every item is in exactly one group. It can do three things: make a new group with just one item, find which group an item is in by naming that group's leader, and merge two groups into one. Groups can join together, but they never split apart. Inside, each group is stored like a little tree with the leader at the top. Two tricks keep it fast: when merging, attach the smaller or shorter tree under the bigger one, and when you look up an item's leader, reconnect the items you passed straight to the leader so next time is quicker.

Union-Find Partition

A disjoint-set data structure (also known as union-find) maintains a partition: a collection of groups where every element belongs to exactly one group. It supports Make-Set(x), which creates a group containing only x; Find(x), which returns a representative element for x's group; and Union(x, y), which merges the two groups if they are different. Two elements are in the same group exactly when Find gives the same representative, which makes it a quick equivalence test. Groups only ever merge, never split. The standard implementation stores each group as a rooted tree whose root is the representative. Two heuristics make it very efficient over many operations: union by rank or size attaches the shorter tree under the taller one, and path compression makes nodes visited during Find point closer to the root.

 

A disjoint-set data structure maintains a mutable partition of elements into pairwise-disjoint sets, supporting Make-Set(x) to create a singleton, Find(x) to return the representative of the unique block containing x, and Union(x, y) to merge the blocks of x and y when they differ. Find provides a stable equivalence test: two elements share a block iff their representatives coincide, as long as no intervening union alters the blocks. The partition only coarsens; there is no split operation. The standard disjoint-set forest represents each block as a rooted tree with parent pointers, the root serving as representative. Union by rank or size bounds tree height by attaching the smaller or shallower tree beneath the other, and path compression rewires nodes on a Find path to point toward the root. Together these heuristics give excellent amortized efficiency over sequences of operations. The recognizing combination is the mutable partition, representative-based equivalence testing, union-only coarsening, forest heuristics, and amortized performance.

Structural Signature

  • A universe of registered elements.
  • A current partition into disjoint blocks.
  • One representative per block.
  • Make-Set, Find, and Union operations.
  • Membership equivalence tested by representative equality.
  • Union-only evolution: blocks merge but do not split in the classic structure.
  • Parent-pointer forest implementation.
  • Roots serving as representatives.
  • Union by rank or size.
  • Path compression during Find.
  • Structural mutations preserving partition semantics.
  • Near-constant inverse-Ackermann amortized complexity for standard operation sequences.
  • Applications requiring incremental connectivity/equivalence.

What It Is Not

It is not set union as a mathematical operation alone, nor a static partition. It is an abstract data type plus implementations maintaining partitions under updates. The disjoint-set forest is the standard implementation, not the only possible realization.[2]

Classic union–find does not support deletion, splitting blocks, arbitrary rollback, or fully dynamic connectivity without extensions. Path compression also changes the internal forest while preserving the represented partition.

Scope of Application

Union–find supports Kruskal’s minimum-spanning-tree algorithm, incremental graph connectivity, connected-component labeling, equivalence-class computation, unification-like tasks, image processing, percolation simulation, and offline least-common-ancestor algorithms.

It excels when the required relation only coarsens. If connectivity edges are deleted or equivalence decisions must be undone, another structure or explicit rollback/persistence scheme is needed.

Clarity

Representatives are identifiers, not necessarily canonical semantic elements. Different union orders and heuristics can select different roots while representing the same partition. Correctness depends on equivalence classes, not on one particular forest shape.

The inverse-Ackermann bound is amortized over a sequence, not a worst-case constant guarantee for each individual operation. Its practical smallness does not make the mathematical distinction disappear.[3]

Manages Complexity

The structure avoids storing each block as a repeatedly copied set. It maintains enough indirection to answer same-block queries and merge blocks cheaply. Path compression invests work during Find to accelerate later operations; rank/size prevents pathological growth during Union.

Abstract Reasoning

  1. Initialize every element as a singleton.
  2. Maintain one parent pointer per forest node.
  3. Follow parents to locate a representative.
  4. Compress the traversed path without changing membership.
  5. Before union, find both roots.
  6. If different, link the lower-rank/smaller tree under the other and update metadata.
  7. Prove that every element has one root and blocks remain disjoint.
  8. Analyze sequences amortized, not operations in isolation.
  9. Reject the classic structure when splits or deletions are required.

Knowledge Transfer

The portable structure is representing an evolving equivalence relation by delegated representatives and cheap irreversible merges. The proposed immediate parent is Data Structure.

Examples

Kruskal. Before adding an edge, compare endpoint representatives; unequal roots mean the edge joins two components, after which the blocks are unioned.

Equivalence declarations. Repeatedly union declared-equal objects, then use Find to enumerate equivalence classes.[4]

Non-example. A graph structure supporting arbitrary edge deletion is not handled by classic union–find alone.

Structural Tensions

  • Abstract partition semantics versus mutable forest shape.
  • Fast amortized sequences versus per-operation worst case.
  • Representative convenience versus canonical identity.
  • Compression speed versus rollback/persistence.
  • Union-only simplicity versus fully dynamic requirements.
  • Theoretical inverse-Ackermann analysis versus practical near-constancy.

Structural–Framed Character

Partition maintenance, representation delegation, irreversible merging, and amortization are structural. Parent arrays, rank, path compression, graph connectivity, and algorithm bounds are computer-science frame.

Structural Core vs. Domain Accent

The portable core is maintaining equivalence classes through representative-based merges. The constitutive accent is the Make/Find/Union contract, forest implementation, heuristics, and complexity analysis.

This entry is a kind of Data Structure.

Data Structure is the broader abstraction this entry instantiates. Partition, Union, Disjointness, Equivalence, Indirection, Compression, and Amortization are related.

Relationships to Other Abstractions

Local relationship map for Disjoint-Set Data StructureParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Disjoint-SetData StructureDOMAINPrime abstraction: Data Structure — is a kind ofData StructurePRIME

Current abstraction Disjoint-Set Data Structure Domain-specific

Parents (1) — outgoing typed relations

  • Disjoint-Set Data Structure is a kind of Data Structure Prime

    Data Structure is the broader abstraction this entry instantiates.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Disjoint-Set Data Structure sits in a sparse region of the domain-specific corpus (84th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25

Not to Be Confused With

  • Mathematical set union.
  • Static partition data.
  • General graph data type.
  • Strongly connected components algorithm.
  • Fully dynamic connectivity.
  • A representative treated as semantic canonical value.
  • Worst-case constant time per operation.

References

[1] Bernard A. Galler and Michael J. Fischer, “An Improved Equivalence Algorithm,” Communications of the ACM 7 (1964): 301–303. registry ↩

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. registry ↩a ↩b

[3] Robert E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, Journal of the ACM 22 (1975): 215–225. registry ↩

[4] Harold N. Gabow and Robert E. Tarjan, “A Linear-Time Algorithm for a Special Case of Disjoint Set Union,” Journal of Computer and System Sciences 30 (1985): 209–221. registry ↩