14. DFS — Depth-First Search

What you'll learn

• 1Write recursive DFS
• 2Write iterative DFS with an explicit stack
• 3Handle visited tracking correctly

Overview

DFS dives deep before backing up. It's natural to write recursively. The two patterns to memorize: pre-order processing (process node before recursing) and post-order (process after children return).

Core Concepts

1. Recursive DFS

import sys
sys.setrecursionlimit(10**6)   # default 1000 — increase for deep graphs!

visited = [False] * (n + 1)

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

for start in range(1, n + 1):
    if not visited[start]:
        dfs(start)

2. Iterative DFS (explicit stack)

def dfs_iterative(start):
    stack = [start]
    visited[start] = True
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                stack.append(v)

3. Connected components

components = 0
for i in range(1, n + 1):
    if not visited[i]:
        dfs(i)
        components += 1
print(components)

4. Grid DFS (4-directional)

DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]

def dfs(r, c):
    visited[r][c] = True
    for dr, dc in zip(DR, DC):
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc] and grid[nr][nc] == 1:
            dfs(nr, nc)

Examples

Example 1 — src/01_recursive_dfs.py

Recursive DFS template with visited array.

Example 2 — src/02_iterative_dfs.py

Iterative DFS — avoids recursion limit issues.

Example 3 — src/03_connected_components.py

Count and label connected components.

Example 4 — src/04_dfs_grid.py

Flood-fill on a 2D grid — classic 'count islands' problem.

Common Mistakes

1. RecursionError because you forgot sys.setrecursionlimit(10**6).
2. Marking visited too late — must set visited[u] = True BEFORE recursing on neighbors.
3. Using a Python list as visited but checking `if u not in visited:` — O(n) per check. Use a set or a list.
4. Forgetting to reset visited between independent queries on the same graph.

Recap

• DFS = recursion + visited array.
• Increase recursion limit for deep graphs.
• Iterative DFS uses an explicit stack — same idea, no recursion limit.

Try It

1. BOJ 2606 (Virus) — count nodes reachable from 1.
2. BOJ 2667 (Numbering apartment complexes) — flood-fill on grid.
3. BOJ 1012 (Cabbage worms) — same idea, different framing.