Union-Find (DSU)
Each set has a representative. Union links two roots, find walks to the root with path compression.
GraphsNear constant per operationNew12 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
connected components with incremental edges
redundant connection
accounts merge
Kruskal
The template
Get this into muscle memory, then adapt the condition per problem.
const p = [...Array(n).keys()];
const find = (x: number): number => (p[x] === x ? x : (p[x] = find(p[x])));
const union = (a: number, b: number) => { p[find(a)] = find(b); }; Watch Union-Find (DSU)If you are stuck
The generic hint ladder for this pattern, in order.
- 1Edges arrive one at a time and you need connectivity now, not later.
- 2Rebuilding a traversal per query is too slow.
- 3Compress paths during find and union by size to keep it flat.
Drill it
Every problem in the bank that uses this pattern.
0 / 12 solved