难度：★★★★☆
类型：图
方法：深度优先搜索
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
题目
在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。
现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。
哪些节点最终是安全的？ 结果返回一个有序的数组。
该有向图有 N 个节点，标签为 0, 1, ..., N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表，满足 (i, j) 是图的一条有向边。
示例：
输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
这里是上图的示意图。
提示：
graph 节点数不超过 10000.
图的边数不会超过 32000.
每个 graph[i] 被排序为不同的整数列表， 在区间 [0, graph.length - 1] 中选取。
解答
根据题目的要求，一个结点安全的前提条件是，从这个结点出发，不会坠入环形区域。因此，可以通过这个法则，对每个结点是否安全作出判断。
图的问题常常可以用深度优先搜索来解决。定义深度优先搜素函数dfs()，函数的输入为图中的某结点，函数的返回值为布尔值，表达了该结点是否是安全的。在函数内部通过递归调用实现判断。
定义一个辅助字典color，用来表达每个结点被染成的颜色，染色的目的在于寻找关联区域，并判断是否坠入环形循环。未被染色的结点定义为白色，判断结果为安全的结点被染色成黑色，其他结点被染成灰色，表达遍历过程中已经遇到过。
在函数入口定义递归终点，即如果当前结点node已经被染过色，如果这个颜色是灰色，说明这个回到了遇到过的位置，也就是说，坠入了环形区域，返回False，否则如果该结点是黑色，说明已经判断过该结点是安全的，返回True。
接下来是对没有遇到过node结点的情况处理。首先把node染成灰色，表示已经在这个结点留下了足迹，然后遍历node结点的所有下一跳结点next_node，只要有任意一个下一跳结点不安全，那么这个结点也是不安全的，判断next_node是否安全可以采用递归调用本函数的方式。
通过了所有下一跳结点的校验，说明当前结点node是安全的，将这个安全的结点染色成黑色，并返回True即可。
我们使用过滤器来过滤出图中所有安全的结点。
import collections
class Solution(object):
def eventualSafeNodes(self, graph):
white, gray, black = 0, 1, 2
color = collections.defaultdict(int)
def dfs(node):
if color[node] != white:
return color[node] == black
color[node] = gray
for next_node in graph[node]:
if not dfs(next_node):
return False
color[node] = black
return True
return list(filter(dfs, range(len(graph))))
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
