Day 20 — Union Find (DSU)

What you’ll learn here

• Disjoint Set Union (DSU) — track connected components and equivalence classes
• Two optimizations: union by rank and path compression — together they make every operation effectively O(1)
• Applications: Kruskal’s MST, cycle detection in undirected graphs, percolation, offline queries
• The amortized analysis behind the inverse Ackermann function (the slowest-growing function you’ll ever see)

DSU is one of the most “bang for the buck” structures in DSA — 30 lines of code, near-constant-time operations, and it unlocks half a dozen classical algorithms.