codaBack to Academy
advanced
Union-Find / Disjoint Set
Union-Find (Disjoint Set Union) is a data structure that tracks a set of elements partitioned into non-overlapping subsets. It supports two primary operations: find (determining which set an element belongs to) and union (merging two sets). With path compression and union by rank optimizations, both operations run in nearly constant amortized time.
Use Cases
- •Kruskal's minimum spanning tree algorithm
- •Detecting cycles in undirected graphs
- •Network connectivity and equivalence class problems
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(1) | O(α(n)) | O(α(n)) |
| Space | O(n) | ||
Visualization
Implementation
Output
Click "Run Code" to see output...