Depth-First Search, Connected Components, And Cycles

What's being tested

Depth-first search questions test whether you can traverse implicit or explicit graphs, mark visited state, and aggregate connected components without double-counting. Expect grids, adjacency lists, island sizing, cycle detection, and recursive-vs-iterative tradeoffs with clear O(V + E) or O(mn) complexity.

Patterns & templates

• Grid DFS — use dfs(r, c) with 4-neighbor deltas; bounds-check before visiting; O(mn) time, O(mn) worst-case stack.

• Connected components — loop over every node/cell, start dfs only if unvisited, increment component count or accumulate size.

• Visited marking — use set(), boolean matrix, or in-place mutation like changing '1' to '0'; avoid revisiting cyclic paths.

• Iterative DFS — replace recursion with explicit stack; safer for large grids or deep graphs where recursion may overflow.

• Cycle detection — for undirected graphs, track parent; for directed graphs, use color states: WHITE, GRAY, BLACK.

• Adjacency construction — convert edge lists into defaultdict(list) before traversal; include isolated nodes if the problem counts them.

• Complexity narration — say O(V + E) for graphs, O(mn) for grids; space is visited plus recursion/stack depth.

Common pitfalls

Pitfall: Marking a cell visited after recursive calls can cause infinite recursion or double-counting; mark before exploring neighbors.

Pitfall: Treating diagonal cells as connected when the prompt specifies 4-directional connectivity.

Pitfall: Using recursive DFS blindly on large inputs; mention iterative DFS when depth could approach V or mn.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.