# 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:

```python
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

| Item | Meaning |
|---|---|
| Input | A directed graph as an adjacency list |
| Output | All eventual safe nodes |
| Terminal node | A node with no outgoing edges |
| Safe node | A node that cannot reach a cycle |
| Required order | Ascending node index |

## Examples

Consider:

```python
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:

```python
[2, 4, 5, 6]
```

Another example:

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

Only node `4` is safe.

So the answer is:

```python
[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:

| State | Meaning |
|---|---|
| `0` | Unvisited |
| `1` | Currently visiting in the active DFS path |
| `2` | Proven safe |

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:

```python
state = [0] * n
```

where `n = len(graph)`.

Define a DFS function:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + e)` | Each node and directed edge is processed at most once |
| Space | `O(n)` | State array plus recursion stack |

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

## Implementation

```python
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:

```python
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:

```python
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:

```python
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:

```python
state[node] = 1
```

Then every outgoing neighbor must be safe:

```python
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:

```python
state[node] = 2
return True
```

The final loop checks nodes in increasing order:

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

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

## Testing

```python
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()
```

| Test | Why |
|---|---|
| Sample graph with cycle | Separates safe terminal paths from cycle paths |
| Graph where only terminal node is safe | Checks unsafe nodes that can reach a cycle |
| Single terminal node | Minimum safe case |
| Self-loop | A node pointing to itself is unsafe |
| Simple chain to terminal | Every node is safe |