Disjoint Set Union is twenty lines of code that answers 'are these two things connected?' fast enough to be free. It is also routinely written with both optimisations copied in and neither understood, which makes the complexity claim look like magic.
The naive version
Every element points at a parent. The representative of a set is the element pointing at itself. Find walks up to the root; union points one root at the other.
Correct, and O(n) per operation in the worst case: union a chain in the wrong order and you build a linked list, then every find walks the whole thing.
Optimisation one: union by size or rank
Always attach the smaller tree under the larger. A node's depth then only increases when its tree merges into one at least as large, so depth is bounded by log n. Worst case becomes O(log n) per operation.
Returning False when the roots already match is worth keeping — it is exactly the cycle-detection signal Kruskal's algorithm needs.
Optimisation two: path compression
On the way back from a find, point every node visited straight at the root. Each find is paid for once and makes all later finds on that path trivial.
Union by rank alone gives O(log n). Path compression alone gives O(log n) amortised. Together they give O(α(n)) amortised, where α is the inverse Ackermann function — below 5 for any input that fits in the universe.
Where it shows up
- →Kruskal's minimum spanning tree — the cycle check is exactly union returning False.
- →Counting connected components — start at n and decrement on every successful union.
- →Detecting a cycle in an undirected graph in one pass.
- →Offline connectivity queries, processed in a convenient order.
- →Grid problems — number of islands, and the classic 'islands after each added land cell'.
What it cannot do
There is no efficient un-union. The structure is one-directional: sets merge and never split. Problems that remove edges over time are usually solved by processing the operations in reverse, turning deletions into insertions — and if you cannot reverse them, DSU is the wrong tool.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.