Find Eventual Safe States
WHAT IT SAYS
In a directed graph, a node is safe if every possible walk starting from it ends at a terminal node; return all safe nodes, sorted.
WHAT IT'S REALLY ASKING
"Read the quantifier twice: EVERY path must terminate — one route into a cycle condemns the node, no matter how many clean exits it also has. So safety isn't reachability (does SOME path work); it's the for-all version, and it propagates backward: a node is safe exactly when ALL of its out-edges point at already-safe nodes. Flip the edges and that's Kahn's peeling with 'all' where 'any' used to be."
Walk forward from each node, hunting for a bad path
O(V · (V + E)) as framed — a full exploration per nodeFor each node, explore all walks leading out of it; if any exploration re-enters a node on its own current path (a cycle), condemn the start; if every branch reaches a terminal, mark it safe.
WHERE THE WORK IS WASTED — Safety verdicts are massively shared and the per-node hunt refuses to share them: if node a's every path runs through node b, then a's verdict IS b's verdict — yet the hunt re-explores b's entire downstream cone once for every ancestor of b. Worse, the framing computes each verdict from scratch in the direction where it is hardest: forward from a node, 'all paths terminate' needs the whole reachable cone examined before ANY conclusion, while backward from the terminals, safety is decided one node at a time by a local counter. The information flows from terminals outward; the naive search swims against it.
Safety flows backward from terminals — a universal Kahn.
Characterise the unsafe set first, because it is the cleaner object: a node is UNSAFE exactly when some path from it reaches a cycle (walks are infinite only by looping, so 'some walk never terminates' ⟺ 'some path enters a cycle'). Safe is the complement: nodes that cannot reach any cycle. Two routes to that complement, and both are old friends upgraded. Route one — the recurrence, read off the quantifier: terminal nodes are safe by definition (no out-edges, every walk has already ended); any other node is safe IFF ALL of its out-neighbours are safe — one unsafe neighbour offers one condemning path. The 'all' is what distinguishes this from reachability's 'any', and it changes the propagation machinery in exactly one place. Reverse every edge, so verdicts can flow from terminals outward along the new direction. On the reversed graph, run Kahn — but where Course Schedule enqueued a node when its FIRST dependency resolved... no: in-degree there counted unmet prerequisites and a node entered the queue at zero, i.e. when ALL were met. The parallel is exact: here, give each node a counter of UNRESOLVED out-edges (its original out-degree); when a node is proven safe, decrement the counter of each original-predecessor (reversed-neighbour); a node whose counter hits zero has had EVERY exit certified safe — enqueue it as newly safe. Nodes whose counters never empty retain at least one edge into the unsafe region: they can reach a cycle. The universal quantifier is implemented by 'wait for the counter to drain', precisely as Kahn implements 'all prerequisites met'. Route two — three-colour DFS, reread: run the directed-cycle detection, and observe what BLACK meant all along: a black node finished its exploration without any path from it hitting a gray ancestor — meaning nothing reachable from it loops — which is the DEFINITION of safe. Gray-hit nodes and everything still gray when a cycle is found are unsafe; memoise verdicts per node (safe / unsafe / unknown) so each node is explored once. Eventual Safe States is the directed-cycle detector with its byproduct promoted to the deliverable. Same answer both ways; the lesson is the pair of rereadings — Kahn's counter generalises from 'prerequisites met' to any universal condition over neighbours, and DFS's black colour was a safety certificate the whole time.
Reverse the graph, drain out-degree counters
O(V + E) time either route, O(V + E) space for the reversal or the colour statesCompute each node's out-degree; build the reversed adjacency list. Enqueue all terminals (out-degree zero). Loop: pop a safe node, mark it, and for each reversed-neighbour decrement its counter, enqueueing on zero. Collect marked nodes, sort, return. (DFS variant: three-colour with memoised safe/unsafe per node, collecting the blacks.)
Drain the Counter for 'All'
YOU'LL SEE IT AGAIN WHEN
- The property is universally quantified over out-edges — every path, every branch — so one bad exit condemns, and verdicts must wait for the last resolution.
- Verdicts originate at sinks/terminals and flow BACKWARD; forward search recomputes shared downstream cones per ancestor.
- A per-node counter of unresolved requirements, decremented as neighbours resolve, implements the universal — zero means proven.