# 802. Find Eventual Safe States

https://leetcode-cn.com/problems/find-eventual-safe-states

# problem 

> 在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。

> 对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。

> 返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

> 该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。

 # example
示例 1：

![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1628172332032/vMdtYPfd7.png)
```
输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。
```
示例 2：
```
输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]
```

# solution

```
/**
 try each node, if node can depth-first search without loop , node is safe.
 dfs 时候由于会遇到访问过的节点，因此需要分情况，这分情况标记：
           0 表示未访问
           1 表示已访问，在父节点上，或者 之前的环 （危险和潜在不安全的节点）
           2 表示已访问，已知的安全节点
 有时会遇到之前访问过的节点，这个时候要看这个节点是否为父节点，或者不安全的节点。
 当安全返回时，需要把父节点的标记，置为安全。
 当非安全返回时，保持父节点的标记，为不安全。
 */
class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] visit = new int[n];
        List<Integer> ret = new ArrayList<>();

        for(int i = 0 ; i < n; i++) {

            if (dfs(i, graph, visit)) {
                ret.add(i);
            }
        }
        return ret;
    }

    public boolean dfs(int i , int[][] graph, int[] visit) {
        // when loop
        if (visit[i] == 0) {
        } else if(visit[i] == 1) {
            return false;
        } else if(visit[i] == 2) {
            return true;
        }
        // push i
        visit[i] = 1;
        int[] neigh = graph[i];
        for(int n: neigh) {
            if(!dfs(n, graph, visit)) {
                return false;
            }
        }
        // pop i;
        visit[i] = 2;
        return true;
    }
}
```