Module 25
Union-Find (DSU)
Track groups that merge over time: find and union, path compression and union by size, component counts, weighted ratios and grid connectivity.
Union-find (also called a disjoint set union, DSU) keeps a collection of groups and answers two questions almost instantly: which group is this item in, and merge these two groups. It doesn't remember paths, only membership, which is exactly what connectivity questions need.
This module builds the structure from a plain parent array, adds the two optimisations that make it nearly O(1) per operation, and applies it to counting components, merging accounts, checking equations, connecting stones, islands that appear one at a time, swaps that sort a string, and ratios between variables.
Best after: Graph Fundamentals
Part 1
Learn the ideas
- 25.1Find and Union with a Parent ArrayEach item points to a parent; the item that points to itself is the group's representative (root). find walks up to the root; union points one root at the other.14 min
- 25.2When Union-Find Beats BFS/DFSUse it when connections arrive over time, when you only need membership, or when you must map unusual items (rows, columns, emails, letters) into groups.10 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
Start with n groups; every successful union removes one.
Equivalence classes: union all equalities first, then check every inequality.
Mapping strings to ids: union emails that appear in the same account, then group by root.
Union a row with a column: stones link them, and each connected group can be reduced to one stone.
Swaps are transitive: within a connected group of indices, any arrangement is reachable, so sort each group.
Dynamic connectivity: land appears one cell at a time and the island count is reported after each.
Weighted union-find: each node stores its ratio to its parent, and find multiplies ratios along the way.