Find Eventual Safe States: Graph Cycle Detection

You have a directed graph and you need to find every node that is guaranteed to be "safe," meaning no matter which path you take from that node, you will eventually reach a terminal node (one with no outgoing edges). That is LeetCode 802: Find Eventual Safe States, and it boils down to one core question: which nodes can reach a cycle? Any node that can reach a cycle is unsafe, and every other node is safe.

The problem

You are given a directed graph with n nodes labeled 0 to n - 1, represented as an adjacency list graph where graph[i] is the list of nodes that node i has edges pointing to. A terminal node is a node with no outgoing edges. A safe node is a node where every possible path starting from that node leads to a terminal node. Return a sorted list of all safe nodes.

Safe nodeUnsafe node (in or reaches cycle)

The approach

The key insight is that a node is unsafe if and only if it can reach a cycle. You can detect this with a DFS coloring technique that uses three states for each node:

1. White (unvisited): the node has not been explored yet
2. Gray (visiting): the node is on the current DFS path, meaning we started exploring it but have not finished
3. Black (visited): the node has been fully processed, and we know whether it is safe or unsafe

Here is how the algorithm works:

1. Start DFS from each unvisited node
2. Mark the node gray when you enter it
3. Recurse on all neighbors. If any neighbor is gray, you have found a cycle, so the current node is unsafe. If any neighbor has already been determined unsafe, the current node is also unsafe
4. Mark the node black when all neighbors have been processed. If no neighbor led to a cycle, the node is safe. Otherwise, mark it unsafe
5. Collect results: after processing all nodes, return the ones marked safe in sorted order

def eventual_safe_nodes(graph: list[list[int]]) -> list[int]:
    n = len(graph)
    color = [0] * n

    def dfs(node: int) -> bool:
        if color[node] != 0:
            return color[node] == 2
        color[node] = 1
        for neighbor in graph[node]:
            if not dfs(neighbor):
                color[node] = 3
                return False
        color[node] = 2
        return True

    return [i for i in range(n) if dfs(i)]

In this code, color[node] uses 0 for white, 1 for gray, 2 for safe (black), and 3 for unsafe. The dfs function returns True if the node is safe and False if it is unsafe. When we encounter a gray node during recursion, it means we have found a back edge in the DFS tree, which signals a cycle.

Step-by-step walkthrough

Let's trace through the DFS coloring algorithm on our example graph where graph = [[1,2],[2,3],[5],[0],[5],[],[]].

The DFS visits each node and edge exactly once. When it backtracks, it propagates the safe or unsafe status up the call stack. Nodes that form or can reach a cycle get marked unsafe, while nodes whose every path terminates cleanly get marked safe.

Complexity analysis

Time: Each node is visited exactly once by the DFS (subsequent calls return immediately from the color check). Each edge is examined exactly once when we iterate over the neighbors of a node. This gives O(V + E) total time, where V is the number of nodes and E is the total number of edges across all adjacency lists.

Space: The color array takes O(V) space. The DFS recursion stack can go as deep as V in the worst case (a long chain of nodes). No additional data structures are needed, so total space is O(V).

The building blocks

DFS three-coloring for cycle detection

The three-color DFS technique is a fundamental pattern in graph algorithms. The white/gray/black coloring scheme comes from the classification of edges in a DFS tree. A back edge (one that points from a node to a gray ancestor) indicates a cycle. By tracking which nodes are currently on the DFS stack (gray), you can detect cycles in a single pass.

This same technique appears in problems like Course Schedule (LeetCode 207), where you need to determine if a directed graph has any cycle. The difference here is that you do not just need to find whether a cycle exists. You need to classify every node as either safe or unsafe based on whether it can reach a cycle.

Terminal nodes and safe propagation

A terminal node has no outgoing edges, so it is trivially safe. The safety property then propagates backward: a node is safe if and only if all of its neighbors are safe. This recursive definition maps directly to the DFS approach. When all recursive calls for a node's neighbors return True, the node itself is safe. If even one neighbor is unsafe or part of a cycle, the node is unsafe too.

Edge cases

• All terminal nodes: If no node has any outgoing edges, every node is a terminal node and therefore safe. The function returns [0, 1, ..., n-1].
• Single large cycle: If all nodes form one big cycle (e.g., 0 -> 1 -> 2 -> ... -> 0), every node is unsafe and the result is an empty list.
• Disconnected components: Nodes in separate components are processed independently. A node in a cycle-free component is safe even if another component contains a cycle.

From understanding to recall

You have seen how three-color DFS identifies safe nodes by detecting which nodes can reach a cycle. The pattern is concise: mark gray on entry, recurse on neighbors, mark safe or unsafe on exit. But writing it from scratch under pressure requires practice. You need to remember the three color states, the early return when a gray node is hit, and the propagation of the unsafe status back up the recursion.

Spaced repetition helps you internalize this pattern. After a few rounds of writing the DFS coloring function from memory at increasing intervals, the white/gray/black framework becomes second nature. When a cycle detection or safe node problem appears in your interview, you will not need to reason through the logic from first principles. You will just write it.

Related posts

• Course Schedule - Topological sort with cycle detection
• Number of Islands - DFS on graphs
• Clone Graph - Graph traversal with BFS/DFS