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.

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.

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.

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¶

Initialize every element as a singleton.
Maintain one parent pointer per forest node.
Follow parents to locate a representative.
Compress the traversed path without changing membership.
Before union, find both roots.
If different, link the lower-rank/smaller tree under the other and update metadata.
Prove that every element has one root and blocks remain disjoint.
Analyze sequences amortized, not operations in isolation.
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.

Relationships to Other Abstractions¶

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

Disjoint-Set Data Structure → is a kind of Data Structure → presupposes, typical Trade-offs → presupposes Constraint

Neighborhood in Abstraction Space¶

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

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Graph Data Type — 0.84
Quotient Graph — 0.83
Graph canonization — 0.82
Yannakakis Algorithm for Acyclic Joins — 0.82
Zero-Sum Problem — 0.80

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