Union-find
Give every group one representative and store, for each element, a pointer toward it. Merging two groups is one write, and asking whether two elements share a group is two walks.
Problems worked on this page, and more to practise
- 684. Redundant Connection
- 721. Accounts Merge
- 778. Swim in Rising Water
- 547. Number of Provinces
- 200. Number of Islands
- 1319. Number of Operations to Make Network Connected
- 990. Satisfiability of Equality Equations
- 1202. Smallest String With Swaps
- 128. Longest Consecutive Sequence
- 399. Evaluate Division
- 952. Largest Component Size by Common Factor
- 1579. Remove Max Number of Edges to Keep Graph Fully Traversable
- 305. Number of Islands II
When should I use union-find instead of DFS?
Use union-find when the connections arrive one at a time and you have to answer questions in between, or when all you need is whether two things are in the same group. A depth-first search answers one such question in time proportional to the whole component, and it has to start again for the next question. Union-find keeps the answer as it builds. Use DFS instead when the graph is given whole and one traversal answers everything, or when you need the path itself rather than the fact that a path exists.
What is path compression, and do I need union by size as well?
Path compression means that after a walk to the root, every element on that walk is re-pointed straight at the root, so the same walk is never made twice. Union by size means the smaller tree is hung under the larger one, which keeps the height at most log n on its own. Either one alone gives you a good bound. Together the amortized cost per operation is the inverse Ackermann function, which is below 5 for any input that fits in memory. In an interview, write both: they are two lines each.
Why does union have to look up the roots first?
A group is named by its root, so every decision union makes is about roots. Writing parent[b] = a re-points b itself, which detaches whatever was hanging under b and leaves its old root claiming members it no longer has. The structure then answers later questions wrongly with no error anywhere. Always write parent[find(b)] = find(a).
How do I count connected components with union-find?
Start a counter at n, one group per element, and lower it by one each time a union actually merges two different groups. The early return inside union is what makes that correct: a union whose two ends already share a root must not lower the count. Have union return a boolean that says whether anything merged, and the counter, cycle detection, and the “is this edge redundant?” question all become one line each.
Can union-find undo a merge or split a group?
Not as it is written here. The structure only ever merges, because path compression throws away the shape that a split would need. If a problem removes edges, the usual answer is to run time backwards: reverse the list of removals so that removing becomes adding, solve it forward with union-find, then reverse the answers. If the problem genuinely needs live deletion, union-find is the wrong tool and you should say so.