# [LeetCode] 802. Find Eventual Safe States 找到最终的安全状态

2021年09月15日 阅读数：1

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.html

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.java

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

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

```Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

```

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]`.

```class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
List<Integer> res = new ArrayList<>();
if(graph == null || graph.length == 0)  return res;

int nodeCount = graph.length;
int[] color = new int[nodeCount];

for(int i = 0;i < nodeCount;i++){
}

return res;
}
public boolean dfs(int[][] graph, int start, int[] color){
if(color[start] != 0)   return color[start] == 1;

color[start] = 2;
for(int newNode : graph[start]){
if(!dfs(graph, newNode, color))    return false;
}
color[start] = 1;

return true;
}
}
```

Python:post

```def eventualSafeNodes(self, graph):
"""
:type graph: List[List[int]]
:rtype: List[int]
"""
n = len(graph)
out_degree = collections.defaultdict(int)
in_nodes = collections.defaultdict(list)
queue = []
ret = []
for i in range(n):
out_degree[i] = len(graph[i])
if out_degree[i]==0:
queue.append(i)
for j in graph[i]:
in_nodes[j].append(i)
while queue:
term_node = queue.pop(0)
ret.append(term_node)
for in_node in in_nodes[term_node]:
out_degree[in_node] -= 1
if out_degree[in_node]==0:
queue.append(in_node)
return sorted(ret)
```

Python:url

```# Time:  O(|V| + |E|)
# Space: O(|V|)
import collections

class Solution(object):
def eventualSafeNodes(self, graph):
"""
:type graph: List[List[int]]
:rtype: List[int]
"""
WHITE, GRAY, BLACK = 0, 1, 2

def dfs(graph, node, lookup):
if lookup[node] != WHITE:
return lookup[node] == BLACK
lookup[node] = GRAY
for child in graph[node]:
if lookup[child] == BLACK:
continue
if lookup[child] == GRAY or \
not dfs(graph, child, lookup):
return False
lookup[node] = BLACK
return True

lookup = collections.defaultdict(int)
return filter(lambda node: dfs(graph, node, lookup), xrange(len(graph)))
```

Python:

```class Solution(object):
def eventualSafeNodes(self, graph):
"""
:type graph: List[List[int]]
:rtype: List[int]
"""
if not graph: return []

n = len(graph)
# 用字段存储每一个节点的父节点
d = {u:[] for u in range(n)}
degree = [0] * n
for u in range(n):
for v in graph[u]:
d[v].append(u)
degree[u] = len(graph[u])

Q = [u for u in range(n) if degree[u]==0]
res = []
while Q:
node = Q.pop()
res.append(node)
for nodes in d[node]:
degree[nodes] -= 1
if degree[nodes] == 0:
Q.append(nodes)
return sorted(res)　```

C++:

```class Solution {
public:
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
vector<int> res;
if (graph.size() == 0) {
return res;
}
int size = graph.size();
vector<int> color(size, 0);         // 0: not visited; 1: safe; 2: unsafe.
for (int i = 0; i < size; ++i) {
if (dfs(graph, i, color)) {     // the i-th node is safe
res.push_back(i);
}
}
return res;
}
private:
bool dfs(vector<vector<int>> &graph, int start, vector<int> &color) {
if (color[start] != 0) {
return color[start] == 1;
}
color[start] = 2;       // mark it as unsafe because it is on the path
for (int next : graph[start]) {
if (!dfs(graph, next, color)) {
return false;
}
}
color[start] = 1;       // mark it as safe because no loop is found
return true;
}
};
```