LeetCode 802: Find Eventual Safe States

Problem Restatement

We are given a directed graph with n nodes labeled from 0 to n - 1.

The graph is represented as an adjacency list:

graph[i]

contains every node that node i points to.

A terminal node has no outgoing edges.

A safe node is a node where every possible path starting from that node eventually reaches a terminal node. If a node can reach a cycle, then it is not safe.

Return all safe nodes in ascending order. The problem statement requires the result to be sorted.

Input and Output

Examples

Consider:

graph = [[1,2],[2,3],[5],[0],[5],[],[]]

The graph has 7 nodes: 0 through 6.

Nodes 5 and 6 are terminal nodes because they have no outgoing edges.

Node 2 points to 5, so it is safe.

Node 4 points to 5, so it is safe.

Nodes 0, 1, and 3 are unsafe because they can reach a cycle involving 0, 1, and 3.

So the answer is:

[2, 4, 5, 6]

Another example:

graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

Only node 4 is safe.

So the answer is:

[4]

First Thought: Brute Force

For each node, we could start a DFS and check whether any path reaches a cycle.

If no path from that node reaches a cycle, the node is safe.

This idea is correct, but doing a full DFS from every node repeats too much work.

A node may appear in paths from many other nodes. Without caching, we may inspect the same subgraph many times.

Key Insight

A node is unsafe if it can reach a directed cycle.

So we can use DFS with states to detect cycles and cache results.

Each node has one of three states:

When DFS reaches a node marked 1, we found a cycle.

When all outgoing neighbors of a node are safe, that node is also safe.

This turns repeated cycle checks into one shared computation.

Algorithm

Create an array:

state = [0] * n

where n = len(graph).

Define a DFS function:

def is_safe(node):
    ...

For each node:

1. If state[node] == 1, return False because we found a cycle.
2. If state[node] == 2, return True because this node is already proven safe.
3. Mark the node as currently visiting.
4. Recursively check every neighbor.
5. If any neighbor is unsafe, return False.
6. If all neighbors are safe, mark the node safe and return True.

Finally, iterate from 0 to n - 1.

Add node i to the result if is_safe(i) returns True.

Because we scan nodes in ascending order, the result is already sorted.

Correctness

The DFS marks a node as 1 while it is in the current recursion path.

If DFS reaches another node that is already marked 1, then the path has returned to a node that is still active. That means there is a directed cycle. Any node that can reach this situation is unsafe, because at least one path can continue forever inside the cycle.

If a node has no outgoing edges, the loop over its neighbors does not find any unsafe neighbor. The node is then marked as safe. This matches the definition of a terminal node.

For a non-terminal node, the algorithm marks it safe only after every outgoing neighbor is safe. Therefore, every path starting from that node must move to a safe node, and from there eventually reach a terminal node.

The algorithm returns false immediately if any outgoing neighbor is unsafe. In that case, there exists at least one path from the node to a cycle, so the node cannot be safe.

Thus the algorithm marks exactly the eventual safe nodes.

Complexity

Here, e is the total number of directed edges in graph.

Implementation

class Solution:
    def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:
        n = len(graph)
        state = [0] * n

        def is_safe(node: int) -> bool:
            if state[node] == 1:
                return False

            if state[node] == 2:
                return True

            state[node] = 1

            for nei in graph[node]:
                if not is_safe(nei):
                    return False

            state[node] = 2
            return True

        answer = []

        for node in range(n):
            if is_safe(node):
                answer.append(node)

        return answer

Code Explanation

The state array stores DFS status:

state = [0] * n

A value of 0 means the node has not been explored yet.

A value of 1 means the node is currently in the active DFS path.

A value of 2 means the node is proven safe.

The first check detects a cycle:

if state[node] == 1:
    return False

If a node appears again while it is still being visited, we have entered a directed cycle.

The second check reuses previous work:

if state[node] == 2:
    return True

Once a node is known to be safe, future DFS calls can return immediately.

Before exploring neighbors, we mark the node as active:

state[node] = 1

Then every outgoing neighbor must be safe:

for nei in graph[node]:
    if not is_safe(nei):
        return False

If any neighbor is unsafe, the current node is unsafe too.

If all neighbors are safe, the current node is safe:

state[node] = 2
return True

The final loop checks nodes in increasing order:

for node in range(n):
    if is_safe(node):
        answer.append(node)

Because of this order, answer is sorted without an extra sort.

Testing

def run_tests():
    s = Solution()

    assert s.eventualSafeNodes(
        [[1, 2], [2, 3], [5], [0], [5], [], []]
    ) == [2, 4, 5, 6]

    assert s.eventualSafeNodes(
        [[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]
    ) == [4]

    assert s.eventualSafeNodes([[]]) == [0]

    assert s.eventualSafeNodes([[0]]) == []

    assert s.eventualSafeNodes([[1], [2], []]) == [0, 1, 2]

    print("all tests passed")

run_tests()