The problem
In a directed graph, a node is safe if every possible path starting from it eventually reaches a terminal node (no outgoing edges). Return all safe nodes in ascending order.
Stuck? Reveal hints one at a time
How to approach it
- 1Run DFS from every node with three states (0 = unvisited, 1 = in progress, 2 = safe).
- 2When visiting a node, mark it "in progress"; recurse into each neighbor.
- 3If any neighbor is "in progress" (cycle) or turns out unsafe, this node is unsafe — leave it gray/failed.
- 4If all neighbors are safe, mark the node safe (2) and memoize.
- 5Collect and return all nodes whose final state is safe.
Key insight
Safe = "cannot reach a cycle". The gray state doubles as cycle detection AND as the unsafe verdict, so one DFS with memoization answers all nodes.
The solution
Watch out for
- A node stuck in state 1 after a failed call must NOT be upgraded later — it genuinely reaches a cycle.
- The reverse-graph + topological-sort solution also works: repeatedly peel terminal nodes.