Union-Find (Disjoint Set Union)
The Disjoint Set Union (DSU), or Union-Find, is a powerful data structure for tracking elements partitioned into disjoint sets. It is the core of algorithms like Kruskal's for Minimum Spanning Trees.
🎥 Video Lectures
- AOI December Camp: DSU – A deep dive from the Algerian Olympiad in Informatics, covering Path Compression, Union by Rank, and applications like Kruskal's algorithm.
- Union-Find in 5 Minutes – A high-speed visual introduction to the
findandunionoperations and their average complexity. - Union-Find Visually Explained – Excellent breakdown of Path Compression and how it achieves near-constant time complexity using the Inverse Ackermann function.
📖 Technical Guides & Implementation
- CP-Algorithms: DSU – The "gold standard" for competitive programming implementation, including advanced optimizations.
- GeeksforGeeks: Intro to DSU – A beginner-friendly guide covering basic array-based implementation.
- Brilliant Wiki: Disjoint Set – Focuses on the logical properties and real-world analogies (like social networks).