Depth-First Search II

Off linked tree nodes, input arrives as a parent array, a 2D grid, or an edge list, and several paths can reach one node. DFS still runs a path to the end before backing up, but now it needs bookkeeping to avoid looping.

Substrate	Bookkeeping needed	Typical use
Tree as parent array	Build child lists first, no visited set	Subtree ranges, preorder tours
2D grid or undirected graph	2 states (unvisited, visited)	Connected components, flood fill
Directed graph	3 states (unvisited, in progress, done)	Cycle detection, safe nodes

Mark a cell or vertex visited when you enter it, before recursing, so two routes into the same node never both descend. A directed graph needs one more state to find a cycle, since reaching a node finished on an earlier branch is harmless. With three states (unvisited, on the current path, done), touching an on-path node means a cycle.

Approach	Time	Extra space
Fresh flood fill from every cell	$O((RC)^2)$	$O(RC)$
One shared visited grid	$O(RC)$	$O(RC)$
Three-color DFS on a directed graph	$O(V + E)$	$O(V)$

Use it to flatten a tree into an array, label connected regions in a grid, or find which vertices of a directed graph reach a cycle.

The problems below start with preorder queries on a tree built from a parent array, move to measuring regions in a 2D grid, and end with three-color cycle detection on a directed graph.