Disjoint Set Union-Find

← Back to Advanced Structures

Tracks a collection of non-overlapping sets. Supports two operations efficiently: find (which set is this element in?) and union (merge two sets).

Key Properties

• Connected Components
• Kruskals Algorithm

Complexity

Nearly O(1) amortized per operation with path compression and union by rank — technically O(a(n)) where a is the inverse Ackermann function.

Related

• Graph Structures (connected components)
• Algorithms (Kruskal’s MST)

---

data-structures advanced union-find