Depth-First Search II

Part I ran DFS on linked tree nodes, where one path reaches every node. Everything else needs more bookkeeping: a tree handed over as a parent array, a 2D grid where a cell has four neighbors and more than one route into it, or a graph built as an adjacency list.

The addition is a visited mark. Mark a node before you recurse into it, never after, or two routes into the same node will both descend. That one change turns tree recursion into connected components and flood fill.

Directed graphs need one state more. "Seen" cannot tell "still open on the current path" from "finished and returned", and only that distinction detects a cycle, so each node carries three colors: unvisited, in progress, done. Reaching an in-progress node is a back edge, which is a cycle.

The problems below start with a tree handed over as a parent array, move to components in a 2D grid, and end with three-color cycle detection on a directed graph.