Lesson 25.2 · Union-Find (DSU)
When Union-Find Beats BFS/DFS
Use 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
Think of it like this
A wedding seating planner adding "these two must sit together" notes one by one. After each note, they can instantly say how many tables are needed, without redrawing the whole seating chart.
1.Typical signals
Dynamic connectivity: edges or cells are added one at a time and you answer after each (Number of Islands II). BFS would restart each time.
Equivalence classes: a == b and b == c means a == c (equations, synonyms, accounts with a shared email). Union the equal things, then check the unequal ones.
Mapped items: union a stone's row with its column, an email with an account, an index with the index it can swap with. Map anything to an integer id (or use a HashMap parent).
Weights on edges to the parent let union-find track ratios or offsets between members (Evaluate Division).
Union-find can't delete edges or tell you a path. For those, use graph traversals.
Remember
- Edges arriving over time.
- Equivalence relations.
- Map non-integer items to ids.
Common mistakes
- Using union-find when the question needs actual shortest paths.