Find Eventual Safe States
Understanding the Problem
We have a directed graph, and we need to find which nodes are "safe." A node is safe if no matter which path you take from it, you always end up at a terminal node, one with zero outgoing edges. If even one path from a node can reach a cycle, that node is unsafe, because following that path can loop forever instead of terminating.
Terminal nodes are safe by definition: there is nowhere to go, so every path (the empty path) terminates. A node is safe when every outgoing edge leads to a safe node, since that guarantees every path from it eventually reaches a terminal.
This reduces to a statement about cycles. The unsafe nodes are exactly those that lie on a cycle or can reach a cycle, and the safe nodes are everything else. So the problem becomes: find all nodes that cannot reach any cycle.
Key Constraints:
n <= 10^4andedges <= 4 * 10^4-> The graph is sparse. A linear O(V + E) traversal is the target; an O(V * E) approach that recomputes reachability per node would be far slower than needed.- The graph may contain self-loops -> A self-loop (a node pointing to itself) makes that node unsafe, since the path from it never leaves the loop. Both approaches below handle this without a special case: the self-loop is a length-one cycle.
Approach 1: DFS with Three-Color Marking
Intuition
Detecting a cycle in a directed graph is the classic use case for DFS with coloring. The standard version uses three colors (or states):
- WHITE (0): The node has not been visited yet.
- GRAY (1): The node is currently on the DFS recursion stack, so we are in the middle of exploring paths from it.
- BLACK (2): The node has been fully processed and its final status is known.
During DFS from a node u, reaching a GRAY node means we have arrived at a node still on the current path, which is a cycle. That makes u and every node on the path back to that GRAY node unsafe. If instead every path from u ends at processed nodes that were all marked safe, then u is safe.
We split the BLACK state into SAFE and UNSAFE so the result of each node is cached. When DFS finishes exploring all neighbors of a node:
- If any neighbor is UNSAFE or sat on the recursion stack (was GRAY when reached), mark the current node UNSAFE.
- If every neighbor is SAFE, mark the current node SAFE.
Because the final status is recorded, each node is computed once and reused on later visits, giving a single linear pass over the graph.
Algorithm
- Create a
colorarray of sizen, initialized to WHITE (0) for all nodes. - For each node
ifrom 0 to n-1, if it hasn't been visited, run DFS on it. - In the DFS for node
u: - Mark
uas GRAY (visiting). - For each neighbor
vofu: - If
vis GRAY, we found a cycle. Return false (unsafe). - If
vis WHITE, recursively DFS onv. If it returns false, return false. - If
vis already marked SAFE, skip it. If it's marked UNSAFE, return false. - If all neighbors are safe, mark
uas SAFE (2) and return true. - If any neighbor was unsafe, mark
uas UNSAFE (3) and return false. - Collect all nodes marked SAFE into the result list.
Example Walkthrough
Code
- Time Complexity: O(V + E). Each node's status is computed once and cached, and each edge is examined once, so the total work is proportional to the number of nodes plus edges.
- Space Complexity: O(V). The color array takes O(V). The recursion stack is O(h) where h is the longest path explored, which is O(V) in the worst case (a single long chain of nodes).
The DFS approach is O(V + E), which is optimal. Its one practical drawback is the recursion: on a deep graph (a long chain of nodes), the call stack can grow to O(V) and overflow. The next approach computes the same answer iteratively, reframing safety as a topological-sort problem on the reversed graph.
Approach 2: Topological Sort on Reverse Graph
Intuition
The definition of safety has a recursive shape that maps directly onto topological sorting. A terminal node (no outgoing edges) is safe. A non-terminal node is safe once all of its outgoing neighbors are known to be safe. This is the same dependency structure Kahn's algorithm resolves, except the "dependency" we count down is a node's out-degree rather than its in-degree.
The algorithm tracks each node's out-degree, which starts as graph[i].length. Terminal nodes have out-degree 0 and are safe immediately. When a node is confirmed safe, every node that points to it has one fewer unresolved dependency, so we decrement those predecessors' out-degrees. To find the predecessors of a node efficiently, we build the reverse graph: for each edge u -> v, we store v -> u. Once a predecessor's out-degree reaches 0, all of its neighbors are safe, so it is safe too and joins the queue.
The reason a node on a cycle is never marked safe: its out-degree can only reach 0 after all of its outgoing neighbors are confirmed safe. Walking around the cycle, each node waits on the next one, which waits on the next, and so on back to the start. That circular dependency never resolves, so no out-degree along the cycle ever drops to 0, and the same holds for any node whose only paths lead into the cycle. Every other node bottoms out at a terminal, so its dependencies resolve in finite time and it is enqueued.
Algorithm
- Build the reverse graph: for each edge u -> v in the original graph, add edge v -> u.
- Compute the out-degree of each node in the original graph, which is
graph[i].length. - Initialize a queue with all terminal nodes (out-degree 0).
- BFS: for each node dequeued (confirmed safe), look at its reverse neighbors. Decrement their out-degree. If a node's out-degree reaches 0, add it to the queue.
- All nodes that were ever added to the queue are safe. Sort and return them.
Example Walkthrough
Code
- Time Complexity: O(V + E). Building the reverse graph takes O(V + E). The BFS processes each node at most once and each edge at most once.
- Space Complexity: O(V + E). The reverse graph stores all E edges in reversed form. The out-degree array, safe array, and queue each take O(V).