1Understand
The idea
Keep a parent pointer per element; two elements are in the same group when they lead to the same root. union links one root under the other, and find compresses the path as it goes. With union by size or rank, each operation is nearly O(1), which makes "are these connected yet?" cheap as edges arrive.
Intuition
Keep a parent pointer per element; two elements are in the same group when they lead to the same root. union links one root under the other; find compresses the path as it goes so future finds are flat.
With union by size or rank, each operation is nearly O(1). That makes "are these connected yet?" cheap as edges arrive, offline connectivity, Kruskal, and redundant-edge problems.
Path compression + union by rank is the default implementation interviewers expect.
What you will be able to do
- Implement find with path compression
- Use union return value to detect cycles
When to use it
- Dynamic connectivity as edges arrive
- Count groups after merges
- Redundant connection / cycle in undirected graph
2See it
Walkthrough
Union by parent
Elements 0..3, union(0,1), union(2,3), find same set?
1 / 5
parent[i]=i. find(x) walks up until parent[x]==x (root).
Live template
Line 1 active
Complexity: time O(α(n)) per op, space O(n)
Almost O(1) per op (inverse Ackermann). Building a full graph and DFS for each edge is slower to write and often O(V + E) per check. Use union-find when connectivity evolves with a stream of unions.
Read the walkthrough as text
Redundant connection. Edges [[1,2],[1,3],[2,3]] form a tree plus one extra.
- Init parent
[0,1,2,3]. - Union
1-2, then1-3, components merge. - Edge
2-3:find(2) == find(3)already → this edge is redundant; return it.
In code:
def find(x):while parent[x] != x:parent[x] = parent[parent[x]]x = parent[x]return x
3Recognise it
Kinds of problems (8)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Count components
Example. Number of connected components in an undirected graph.
How. Union edges; components = n, successful unions count (with path compression).
Redundant connection
Example. First edge that creates a cycle.
How. Union on each edge; first edge whose endpoints already share a root.
Accounts merge (union by key)
Example. Union accounts that share an email.
How. Map email → id; union ids per account; group by root.
Union by rank or size
Example. Keep trees shallow for near-constant find.
How. Attach smaller rank under larger; path-compress in find.
Grid union-find (islands as they appear)
Example. Dynamic island count as land cells are added.
How. Union with 4 neighbours when cell flips to land; adjust count on new vs merged.
Is the graph a tree? (one component, no cycle)
Example. Validate n−1 edges connect all nodes acyclically.
How. n−1 edges and one component after unions, extra edge or disconnect fails.
Process edges in value order
Example. Kruskal-like processing without explicit MST output.
How. Sort edges by weight; union when endpoints differ.
Separate structures per edge type
Example. Connectivity with multiple edge colours.
How. One DSU per type, or tag roots by type when merging is type-specific.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Links nodes, not roots
Why it happens. parent[a]=b directly links the two indices you saw on the edge.
How it fails. Chain 0→1→2: union(2,3) sets parent[2]=3 but root of 2 is still 0, components wrong.
Fix. ra, rb = find(a), find(b); if ra != rb: parent[ra] = rb (or union by rank).
No path compression
Why it happens. Find without compression still walks to root correctly.
How it fails. Skewed parent chain length n, m finds degrade to O(n·m).
Fix. Path compression: parent[x] = parent[parent[x]] while walking find.
Component count drift
Why it happens. Decrementing on every union call is easy bookkeeping.
How it fails. union returns false (already connected) but count-- anyway, reaches negative components.
Fix. Decrement only when find roots differ and union actually merges.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.