DSU with Path Compression
Find and union in near-constant time.
What a DSU Tracks
A Disjoint Set Union keeps items grouped into non-overlapping sets, so you can ask if two things already belong together. 🤝
Sets as Trees
DSU stores each set as a tree. Every element points to a parent, and the topmost node, the root, is the unique name of the whole group.
All lessons in this course
- DSU with Path Compression
- Union by Rank and Components
- Kruskal's Minimum Spanning Tree
- Prim's MST with a Heap