Python Snippet

Union-Find in Python

Difficulty: Hard

Union-Find (Disjoint Set Union, DSU) tracks 'which group does each element belong to' and answers `find` / `union` in nearly O(1) amortized when you implement both path compression and union by rank. It is the right data structure for connected-components, Kruskal's MST, and 'is X equivalent to Y' under a stream of merges. This entry covers a basic class, the rank + path compression upgrades, and an MST application.