Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count the isolated 'islands' of nodes in an undirected graph. Either flood each unvisited node with DFS/BFS and count how many floods you launch, or use Union-Find: start with n components and decrement the count once per edge that joins two previously-separate groups. The optimal answer is Union-Find with path compression + union by rank — near O(n + e·α(n)).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise a counting-groups problem maps to either graph traversal or a disjoint-set structure, and whether you can implement Union-Find correctly — especially decrementing the count only on a real merge.
Where candidates slip
Decrementing the component count on every edge instead of only when find(a) != find(b), which undercounts whenever an edge connects two already-joined nodes.
How to stand out
Offer both: DFS for clarity, Union-Find for dynamic connectivity. Mention path compression + union by rank give near-constant amortised ops (inverse Ackermann), and that 'count = n − successful unions' is the invariant.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount connected components (undirected)Edges static or streaming?Static, one shotStreaming / many connectivity queriesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
DFS Flood From Each Unvisited Node
1Hint 1Explore hintHide hint
If you start at a node and walk every edge you can reach, you've discovered one entire component. How many times do you have to RESTART that walk to cover the whole graph?
2Hint 2Explore hintHide hint
Build an adjacency list from the edge pairs (both directions, it's undirected). Keep a visited array.
3Hint 3Explore hintHide hint
Loop over all n nodes; each time you hit an unvisited one, increment a counter and DFS-flood everything reachable from it, marking visited. The counter is the answer.
A · Core idea
Treat each component as a region to flood-fill. Walk every node; whenever you find one you haven't seen, that's a brand-new component, so bump the count and flood everything reachable from it.
Why one flood equals one component. A DFS (or BFS) launched from a node visits exactly the set of nodes reachable from it — which is precisely its connected component. So the number of times you have to start a fresh flood is the number of components. Marking nodes visited as you go guarantees you never start a second flood inside a component you've already counted.
Why you must convert edges to an adjacency list first. The input is a flat list of pairs — great for Union-Find, useless for DFS, which needs to ask 'who are node x's neighbours?' in O(1). Since the graph is undirected, each edge [a,b] goes into both adj[a] and adj[b]; forgetting the second direction silently splits components in two.
Why it's clean but not always ideal. It's O(n + e) and very readable. The limitation is that it answers one static snapshot — if edges arrive over time and you keep asking 'are these two connected now?', you'd re-flood repeatedly. That dynamic-connectivity scenario is exactly where Union-Find pulls ahead.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5, edges = [[0,1],[1,2],[3,4]]Array state
flood from 0
visit 0,1,2 — component #1
2C · Code with teaching comments
Reference implementation previewpublic int countComponents(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]);Explore the full codeHide the full code
D · Why it works and complexityO(n + e) timeO(n + e) spaceOpen the invariant and proofExplore the proofHide the proof
Component counting reduces to 'how many independent flood-fills cover the graph?'. The visited array is what makes each component get counted exactly once — it's the same trick as Number of Islands, just on an explicit graph instead of a grid.
ComplexityO(n + e) time, O(n + e) space — Building the adjacency list is O(e); the DFS visits each node once and traverses each edge twice (both directions) → O(n + e) time. Adjacency list O(n + e), visited array and recursion stack O(n) → O(n + e) space.
E · Edge cases and pitfalls5n = 4, edges = [] — No edges → every node is unvisited when reached → 4 separate floods → 4.Explore edge casesHide edge cases
Edge cases handled
n = 4, edges = []No edges → every node is unvisited when reached → 4 separate floods → 4.n = 1, edges = []Single node → one flood → 1 component.
Pitfalls
- Adding only one direction per edge — undirected graph gets split, overcounting components.
- Incrementing count inside the DFS instead of in the outer loop — counts nodes, not components.
- Deep recursion on a long chain can overflow the stack — use an explicit stack / BFS for very large n.
Approach 2 of 2 · Optimal
Union-Find with Path Compression + Union by Rank (Optimal)
1Hint 1Explore hintHide hint
Forget traversal. Start by assuming all n nodes are separate islands — count = n. What happens to the count each time an edge genuinely joins two different islands?
2Hint 2Explore hintHide hint
Use a disjoint-set (Union-Find): parent[] array, find(x) follows parents to the root, union(a,b) links one root under the other. Decrement count only when find(a) != find(b).
3Hint 3Explore hintHide hint
Add path compression (point nodes straight at the root during find) and union by rank (attach the shorter tree under the taller). Together they give near-constant amortised operations.
A · Core idea
Model connectivity directly with a disjoint-set forest. Every node starts as its own root (n components); each edge tries to merge its two endpoints, and the count drops by one only when the merge actually joins two distinct sets.
Why 'count = n − successful unions' is the whole algorithm. Initially nothing is connected, so there are n components. Joining two separate components reduces the total by exactly one. Joining two nodes that are already in the same component changes nothing (it'd be a redundant edge / cycle). So if you decrement only on a successful union — when find(a) != find(b) — the running count is always the exact number of components. Decrementing on every edge is the classic bug; it undercounts whenever the graph has a cycle.
Why path compression matters. find(x) walks parent pointers up to the root. Without compression those chains can grow to length n, making find O(n). Path compression re-points every node on the path directly to the root as it returns, so future finds on those nodes are O(1). It flattens the tree opportunistically, for free, during queries you were doing anyway.
Why union by rank matters. When merging two trees, attach the shorter one under the taller one's root. This keeps trees shallow — height grows only when two equal-rank trees merge. Combined with path compression, the amortised cost per operation is the inverse Ackermann function α(n), which is ≤ 4 for any input you'll ever see — effectively constant.
Why it beats DFS here. Same near-linear cost on a static graph, but Union-Find is incremental: feed edges one at a time and it maintains the component count and answers 'connected?' in near-O(1) without ever re-traversing. That's why it's the canonical answer for dynamic-connectivity and cycle-detection variants.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5, edges = [[0,1],[1,2],[3,4]]Interactive diagram
Disjoint-set forest after all unions
initTwo trees remain — {0,1,2} rooted at 0 and {3,4} rooted at 3 — so count ended at 2.
2C · Code with teaching comments
D · Why it works and complexityO(n + e·α(n)) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Union-Find turns 'are these in the same group, and how many groups are there?' into two near-constant operations. The mental model is a forest of trees where each tree is a component and its root is the component's id; the two optimisations exist solely to keep those trees pancake-flat so find never walks far.
ComplexityO(n + e·α(n)) time, O(n) space — Each of the e edges does two finds and maybe a union; with path compression + union by rank, each operation is amortised α(n) (inverse Ackermann ≈ constant). Plus O(n) init → O(n + e·α(n)) time, O(n) for the parent and rank arrays.
E · Edge cases and pitfalls5n = 3, edges = [[0,1],[1,2],[0,2]] — First two unions drop count 3→2→1; edge [0,2] finds equal roots → no decrement → 1. This is the cycle case the find-check guards against.Explore edge casesHide edge cases
Edge cases handled
n = 3, edges = [[0,1],[1,2],[0,2]]First two unions drop count 3→2→1; edge [0,2] finds equal roots → no decrement → 1. This is the cycle case the find-check guards against.n = 4, edges = []No edges → no unions → count stays 4.
Pitfalls
- Decrementing count on every edge instead of only when find(a) != find(b) — undercounts on cycles.
- Omitting path compression or union by rank — find chains degrade toward O(n), losing the near-constant guarantee.
- Recursive find without compression on a long chain — slow and risks stack overflow for large n.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int countComponents(int n, int[][] edges) { int[] parent = new int[n]; int[] rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; int count = n;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Decrementing on every edge
An edge between two nodes already in the same component must NOT reduce the count. Decrementing unconditionally undercounts every time the graph contains a cycle or a duplicate edge.
Explore the code comparisonHide the code comparison
Decrementing on every edge
An edge between two nodes already in the same component must NOT reduce the count. Decrementing unconditionally undercounts every time the graph contains a cycle or a duplicate edge.
Don't write this
count = n
for a, b in edges:
union(a, b)
count -= 1 # wrong: also fires on redundant edgesWrite this instead
count = n
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb: # only a genuine merge
union(ra, rb)
count -= 12One-directional adjacency list
The graph is undirected, so edge [a,b] must appear in both adj[a] and adj[b]. Adding only adj[a] makes the DFS unable to reach a from b, splitting a single component into two.
Explore the code comparisonHide the code comparison
One-directional adjacency list
The graph is undirected, so edge [a,b] must appear in both adj[a] and adj[b]. Adding only adj[a] makes the DFS unable to reach a from b, splitting a single component into two.
Don't write this
for (int[] e : edges) {
adj.get(e[0]).add(e[1]); // only one direction
}Write this instead
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]); // undirected → both directions
}3Find without path compression
A plain find that walks parents to the root can traverse an O(n) chain on a skewed tree, making the whole algorithm O(n·e). Compressing the path during find keeps subsequent lookups near O(1).
Explore the code comparisonHide the code comparison
Find without path compression
A plain find that walks parents to the root can traverse an O(n) chain on a skewed tree, making the whole algorithm O(n·e). Compressing the path during find keeps subsequent lookups near O(1).
Don't write this
def find(x):
while parent[x] != x:
x = parent[x] # no compression — chains stay long
return xWrite this instead
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return xRevise
Carry the pattern into the interview
Pattern to remember
Connected-components count via DFS flood or Union-Find
Code pattern to memorize
Union-Find:
count = n
for (a, b) in edges:
if find(a) != find(b): union(a, b); count--
return count
# count drops only on a SUCCESSFUL union (different roots)Rules to remember
- 1Start the component count at n (every node its own island) and decrement once per successful union — never on an edge whose endpoints already share a root.
- 2Build an adjacency list for the DFS version — edges come as a pair list, not an adjacency structure, so convert first.
- 3DFS/BFS: count a new component only when you start a flood from an unvisited node; mark visited as you go to avoid recounting.
- 4Union-Find needs path compression AND union by rank/size to get near-O(1) per op — skipping either degrades toward O(n) find chains.
- 5The graph is undirected, so each edge
[a,b]connects both ways — add both directions in the adjacency list.
Use this pattern when
- Count groups / islands / clusters in an undirected graph
- Dynamic connectivity — edges arrive and you ask 'same group?' repeatedly
- Detect whether adding an edge creates a cycle (endpoints already connected)
- Merge-as-you-go problems (accounts merge, friend circles, Kruskal's MST)
Choose another pattern when
- Directed graph + reachability → that's SCCs (Tarjan/Kosaraju), not plain components
- Need the actual shortest path between nodes → BFS/Dijkstra, not component counting
- Single connectivity query, no merging → a plain DFS/BFS is simpler than DSU
- Weighted MST asked, not a count → Union-Find is a building block but the answer is the tree, not the component count
Interview takeaway
Connected components is the 'hello world' of Union-Find: n disjoint sets, one decrement per genuine merge. Once you internalise 'count = n minus the number of successful unions', you'll reuse the same DSU for Redundant Connection, Accounts Merge, Number of Provinces, and Kruskal's MST.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Disjoint-Set Union (Union-Find). Recognise it whenever you count groups, test dynamic connectivity, or detect cycles in an undirected graph — n disjoint sets, merge on each real edge. Same engine behind Number of Provinces, Redundant Connection, Accounts Merge, and Kruskal's MST.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Number of ProvincesComing soonSame component count, but the graph is given as an adjacency matrix — Union-Find or DFS over the matrix.
- Redundant ConnectionComing soonUse Union-Find to find the edge whose endpoints already share a root — that edge closes the cycle.
- Number of IslandsConnected components on a grid — DFS flood or Union-Find over cells.
- Graph Valid TreeA tree is exactly one component with n−1 edges and no cycle — Union-Find checks both at once.