Strongly Connected Pieces — Solution & Editorial

Back to the Problem

Kosaraju (two DFS passes: finish order on G, then flood on the reverse graph) or Tarjan's lowlink — both linear. Recursive DFS overflows stacks at these sizes; use an explicit stack.

Complexity: O(N + M)

Watch out: Iterative DFS or a raised recursion limit — 10⁴-deep recursion crashes most defaults.