> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/802-find-eventual-safe-states.md).

# 802 Find Eventual Safe States

## 802.[ Find Eventual Safe States](https://leetcode.com/problems/find-eventual-safe-states/description/)

## 1. Question

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is\_eventually safe \_if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number`K`so that for any choice of where to walk, we must have stopped at a terminal node in less than`K`steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has`N`nodes with labels`0, 1, ..., N-1`, where`N`is the length of`graph`. The graph is given in the following form:`graph[i]`is a list of labels`j`such that`(i, j)`is a directed edge of the graph.

```
Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output:
[2,4,5,6]
Here is a diagram of the above graph.
```

![](/files/-LyrLKC4Kle8WpKLeDa8)\
**Note:**

* `graph`will have length at most`10000`.
* The number of edges in the graph will not exceed`32000`.
* Each`graph[i]`

  will be a sorted list of different integers, chosen within the range`[0, graph.length - 1]`.

## 2. Implementation

**(1) BFS Topological Sort**

```java
class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        // Method 1: BFS topologicl sort
        List<Integer> res = new ArrayList<>();

        if (graph == null || graph.length == 0) {
            return res;
        }

        int n = graph.length;
        int[] outDegree = new int[n];

        List<Set<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }

        for (int i = 0; i < n; i++) {
            for (int neighbor : graph[i]) {
                adjList.get(neighbor).add(i);
                ++outDegree[i];
            }
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (outDegree[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int curNode = queue.remove();
            res.add(curNode);

            for (int nextNode : adjList.get(curNode)) {
                if (--outDegree[nextNode] == 0) {
                    queue.add(nextNode);
                }
            }
        }

        Collections.sort(res);
        return res;
    }
}
```

## 3. Time & Space Complexity

**BFS Topological Sort:**&#x20;