Find Eventual Safe States
Last Updated: April 5, 2026
Understanding the Problem
We have a directed graph, and we need to figure out 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. The moment any path from a node can reach a cycle, that node becomes unsafe.
Think about it this way: if you're standing at a node and you follow edges randomly, can you ever get stuck in an infinite loop? If the answer is yes for even one possible path, that node is not safe. Terminal nodes are trivially safe since there's nowhere to go. And nodes that only point to safe nodes are also safe, because every path from them eventually terminates.
The core insight is that unsafe nodes are exactly those that lie on a cycle or can reach a cycle. So this problem boils down to: find all nodes that cannot reach any cycle in the graph.
Key Constraints:
n <= 10^4-> We can afford O(n^2) at most, but O(n + E) is ideal. This rules out all-pairs approaches but keeps single-pass graph traversals on the table.edges <= 4 * 10^4-> The graph is relatively sparse. Combined with n up to 10^4, we need algorithms that are linear in V + E.- The graph may contain self-loops -> A self-loop (node pointing to itself) immediately makes that node unsafe. Our solution needs to handle this naturally.
Approach 1: DFS with Three-Color Marking
Intuition
The first thing that comes to mind when we hear "cycle detection in a directed graph" is DFS with coloring. The classic approach uses three colors (or states):
- WHITE (0): The node hasn't been visited yet.
- GRAY (1): The node is currently on the DFS recursion stack, meaning we're in the middle of exploring paths from it.
- BLACK (2): The node has been fully processed, and we know its final status.
Here's the key idea: if during DFS from node u, we reach a GRAY node, we've found a cycle. That means u (and every node on the path back to that GRAY node) is unsafe. But if all paths from u lead to BLACK nodes that were marked safe, then u is safe too.
We can refine our coloring slightly. Instead of just BLACK, we track whether a fully processed node is SAFE or UNSAFE. When we finish exploring all neighbors of a node:
- If any neighbor is UNSAFE or led to a cycle (was GRAY when we found it), mark the current node UNSAFE.
- If all neighbors are SAFE, mark the current node SAFE.
This way, each node is visited at most once, and we get our answer in a single DFS pass over the entire 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 is visited at most once by DFS. Each edge is examined exactly once. So the total work is proportional to the number of nodes plus edges.
- Space Complexity: O(V). The color array takes O(V) space. The recursion stack can go up to O(V) deep in the worst case (a long chain of nodes).
The DFS approach is already O(V + E), which is optimal. But recursive DFS has a practical weakness: for very deep graphs, the recursion stack can overflow. The next approach solves the same problem iteratively using a completely different perspective.
Approach 2: Topological Sort on Reverse Graph
Intuition
Let's flip the problem on its head. Instead of asking "which nodes can reach a cycle?", let's ask "which nodes can be reached from terminal nodes when we reverse all edges?"
Here's the reasoning:
- Terminal nodes (no outgoing edges) are definitely safe.
- In the original graph, a node is safe if ALL of its outgoing neighbors are safe.
- If we reverse the graph, a terminal node in the original becomes a node with zero in-degree in the reversed graph.
So the algorithm works on the original graph's out-degree. We track each node's out-degree. When a neighbor is confirmed safe, we decrement the out-degree. Once a node's out-degree reaches 0 (all neighbors are safe), we add it to the queue and mark it safe. This is essentially Kahn's algorithm applied to out-degree in the reverse graph.
The topological sort approach mirrors the definition of safety in reverse. A terminal node is safe by definition. A non-terminal node is safe only if all its neighbors are safe. By working backwards from terminal nodes and peeling off layers, we compute this definition iteratively.
When we decrement a node's out-degree and it hits zero, it means every node it originally pointed to has already been confirmed safe. Nodes involved in cycles will never have their out-degree reach zero because the cycle creates a circular dependency that can never be resolved.
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 (this is just
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).