1Understand
The idea
From a starting node, go as deep as possible, marking every node as visited when you first reach it so you never process it twice. Starting a DFS from every unvisited node counts connected components; on a grid, the neighbours are the four adjacent cells.
Intuition
From a starting node, go as deep as possible, marking every node visited when you first reach it so you never process it twice. Starting a DFS from every unvisited node counts connected components; on a grid, neighbours are the four (or eight) adjacent cells.
DFS builds recursion stacks naturally for path existence, cycle detection in undirected graphs (back edge to a visited non-parent), and flood fill.
Marking on entry (not on exit) is what prevents infinite loops in cyclic graphs.
What you will be able to do
- Mark visited before recursing
- Build an adjacency list from edges
When to use it
- Count islands or connected components
- Is there a path?
- Clone or explore a graph
2See it
Walkthrough
Connected components
Nodes 0-3, edges 0-1, 2-3, DFS marks a whole component.
1 / 4
seen empty. Start DFS at 0; mark and recurse to neighbors.
Live template
Line 2 active
Complexity: time O(V + E), space O(V)
Time O(V + E), on a grid O(rows · cols). Space O(V) for the recursion/visited stack in the worst flood. Union-find also counts components; DFS is usually simpler for grids.
Read the walkthrough as text
Number of islands. Grid with land '1' and water '0': In code:
1 1 01 0 00 0 1
- Scan cells; at the first
'1', start DFS/BFS flood fill, sinking visited land to'0'(or a visited set). - That fill clears the 3-cell island; component count becomes 1.
- Later the lone
'1'starts a second fill → answer2.
In code:
def dfs(r, c):if not in_bounds or grid[r][c] != '1': returngrid[r][c] = '0'for nr, nc in neighbours: dfs(nr, nc)
3Recognise it
Kinds of problems (11)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Reachability (is there a path?)
Example. Can you reach target from source in an undirected graph?
How. DFS from source with seen; answer is target in seen.
Connected components / islands
Example. Count number of islands in a grid.
How. DFS flood fill each unvisited ‘1’; each start increments component count.
Flood fill on a grid
Example. Recolor connected region from click.
How. DFS same-color neighbours; paint as you go.
Clone a graph
Example. Deep copy an adjacency-list graph.
How. Map node → clone; DFS neighbours and wire clone edges once.
Cycle detection (directed, three colours)
Example. Does a directed graph have a cycle?
How. White/grey/black: back edge to grey means cycle.
Bipartite check
Example. 2-color the graph if possible.
How. DFS assign colour; conflict if neighbour already has same colour.
Eulerian path (Hierholzer)
Example. Find route using every edge once.
How. DFS and post-order stack edges; reverse pops to build path.
Weighted relations (ratios between variables)
Example. Equations like a/b = k, evaluate queries.
How. Build weighted undirected graph; DFS finds path product along components.
Count edges that point the wrong way
Example. Minimum edge reversals to make a tree rooted at 0.
How. Rooted DFS counts edges away from parent direction.
Bridges and articulation points (low-link)
Example. Find critical edges in an undirected graph.
How. DFS with disc/low; tree edge with low[child] > disc[u] is a bridge.
Strongly connected components
Example. Partition a directed graph into SCCs.
How. Kosaraju (two-pass DFS) or Tarjan with low-link on one DFS.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
No visited set
Why it happens. DFS revisits nodes on cycles forever.
How it fails. Undirected edge (1,2) twice in recursion with no seen, infinite loop.
Fix. Mark visited on entry (or colour for directed cycles) before recursing.
One-way edges
Why it happens. Each edge added only u → v, so DFS from v never reaches u.
How it fails. Components count = 2 on a single connected pair because reverse edge missing.
Fix. For undirected graphs, append v to adj[u] and u to adj[v].
Isolated nodes missed
Why it happens. Only nodes mentioned in edges get visited.
How it fails. n = 5 with one edge 0-1; node 4 never in adjacency, you report one component instead of three.
Fix. Iterate all nodes 0..n−1; start DFS when unvisited.
Parent edge as a back edge
Why it happens. Undirected bridge DFS treats the tree edge back to parent as a back edge.
How it fails. low[child] lowered through parent, every edge looks internal, no bridge found.
Fix. Skip the only parent when recursing to neighbours (pass parent id).
Wrong low-link test
Why it happens. Bridge vs articulation use different low-link inequalities.
How it fails. Use low[child] >= disc[u] to detect bridges, you mark non-bridge tree edges as bridges.
Fix. Bridge: low[child] > disc[u]; articulation (non-root): low[child] >= disc[u].
DFS root rule
Why it happens. Every node with low condition flagged as articulation, including leaves.
How it fails. DFS root with one child labeled articulation, root needs ≥ 2 DFS children.
Fix. Root is articulation only if it has two or more children in the DFS tree.
Second pass on the wrong graph
Why it happens. Kosaraju's second pass must follow reversed edges.
How it fails. Second DFS on original edges, components merge incorrectly.
Fix. First pass order on G; second pass DFS on reversed graph G^T in that order.
Finished nodes still on the stack
Why it happens. In Tarjan, updating low from a node already assigned to another SCC.
How it fails. Edge to finished component lowers low incorrectly, SCCs split wrong.
Fix. Only relax low from neighbours still on the recursion stack (in the same unfinished SCC).
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.