Overview
Union-Find stores each element's parent in a forest of set representatives. Path compression and union by rank or size keep trees shallow across many connectivity queries.
CoreSource checked
Union-Find
Maintains disjoint sets with near-constant-time find and union operations.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Disjoint Set
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 9
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Disjoint Set Union, DSU
Core Concepts
representative parentpath compressionunion by rankconnected componentstored invarianttree structuredisjoint setinvariant maintenance
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(alpha(n))
Worst
O(alpha(n))
Space
O(n)
When to Use
- Use when connectivity only needs additions, not deletions.
- Use when many union and find operations occur over a fixed universe.
When Not to Use
- Avoid when edges must be deleted or historical versions queried without a persistent variant.
- Avoid when the set universe cannot be indexed or mapped consistently.
What It Does
- Finds the representative of an element's set
- Unites two sets by linking representatives
- Compresses paths to speed future finds
Use Cases
- Dynamic connectivity in undirected graphs
- Kruskal's minimum spanning tree algorithm
- Grouping equivalent items
Inputs
- Items
- Union operations
- Find queries
Outputs
- Set representatives
- Connectivity answers
Pseudocode
- 1.Initialize each element as its own parent
- 2.For find(x), follow parents to the root
- 3.Compress parent pointers on the way back
- 4.For union(a, b), find both roots
- 5.Attach the smaller-rank or smaller-size root under the other
Canonical Example
- Input
- union(A, B), union(C, D), union(B, C), find(A)
- Output
- same representative as D
- Explanation
- The third union connects the two groups, so A and D become part of one set.
Implementation Notes
- Initialize parent[x] = x for every element.
- Use union by size or rank along with path compression.
- Test repeated unions of already-connected elements.
Common Pitfalls
- Union must link roots, not arbitrary nodes.
- Path compression changes parent pointers and can break rollback variants.
- Forgetting initialization makes singleton sets invalid.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow parent trees flattening as finds compress paths.
Step 1 of 5: Initialize each element as its own parent
disjoint-set-forestNotes
Union-Find is excellent for incremental connectivity but does not handle deletions directly.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookReference for disjoint-set union operations, path compression, union by rank, and near-constant amortized behavior.
Efficiency of a Good But Not Linear Set Union Algorithm
PaperOriginal analysis reference for disjoint-set union operations, path compression, and inverse-Ackermann behavior.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsPersistent Union-Find
Data Structures · Specialized
Persistent union-find is a versioned disjoint-set structure that preserves historical connectivity states.
Compare with thisUsed byConnected Component Labeling
Image Processing · Core
Connected-component labeling can merge provisional labels efficiently with union-find.
Compare with thisUsed byKruskal's Algorithm
Graph Traversal · Core
Kruskal's algorithm uses union-find to detect whether an edge connects two components.
Compare with thisUsed byTarjan's Offline LCA
Graph Traversal · Extended
Tarjan's offline LCA answers ancestor queries by combining DFS traversal with union-find sets.
Compare with thisRelationships
View full relationship pageUsed byKruskal's Algorithm
Kruskal's algorithm uses union-find to detect whether an edge connects two components.
Conceptual neighborConnected Components
Union-Find maintains component membership under incremental unions.
Related Algorithms
Tags
Data StructureGraph ConnectivityTree