难度：★★★★☆
类型：图
方法：深度优先搜索

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。

现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 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解决方案，请移步力扣中等题解析