找到最终的安全状态

难度: Medium

有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示， graph[i]是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i]中的每个节点都有一条边。

如果一个节点没有连出的有向边，则该节点是 终端节点 。如果从该节点开始的所有可能路径都通向 终端节点 ，则该节点为 安全节点 。

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

示例 1：

Illustration of graph

输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。
节点 5 和节点 6 是终端节点，因为它们都没有出边。
从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。

示例 2：

输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]
解释:
只有节点 4 是终端节点，从节点 4 开始的所有路径都通向节点 4 。

提示：

n == graph.length
1 <= n <= 10⁴
0 <= graph[i].length <= n
0 <= graph[i][j] <= n - 1
graph[i] 按严格递增顺序排列。
图中可能包含自环。
图中边的数目在范围 [1, 4 * 10⁴] 内。

Submission

运行时间: 70 ms

内存: 22.0 MB

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        c = [0] * n

        def dfs(x: int) -> bool:
            if c[x] > 0:
                return c[x] == 2

            c[x] = 1
            for y in graph[x]:
                if not dfs(y):
                    return False
            c[x] = 2
            return True

        return [i for i in range(n) if dfs(i)]

Explain

该题解使用了深度优先搜索（DFS）的思路。首先创建一个长度为 n 的数组 c 用于记录每个节点的状态：0 表示未访问，1 表示正在访问，2 表示已确定为安全节点。然后对每个节点执行 DFS 遍历，判断从该节点出发是否能到达环或终端节点。如果在 DFS 过程中遇到了已访问的节点，说明存在环，直接返回 False；如果该节点是终端节点或者从该节点出发的所有相邻节点都是安全节点，则将该节点标记为安全节点。最后，将所有被标记为安全节点的节点编号以列表形式返回。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        c = [0] * n  # 记录节点状态，0:未访问，1:正在访问，2:安全节点

        def dfs(x: int) -> bool:
            if c[x] > 0:
                return c[x] == 2  # 如果节点已访问，根据其状态判断是否为安全节点

            c[x] = 1  # 标记节点为正在访问
            for y in graph[x]:
                if not dfs(y):  # 对相邻节点执行 DFS，如果有环或不安全，则返回 False
                    return False
            c[x] = 2  # 标记节点为安全节点
            return True

        return [i for i in range(n) if dfs(i)]  # 对每个节点执行 DFS，并返回所有安全节点

Explore

是的，足够。在DFS中，当遇到已被访问的节点y，可以根据y的状态直接判断。如果y的状态为2（安全节点），则可以继续递归调用其它相邻节点，因为安全节点y不会导致环的出现。如果y的状态为1（正在访问），说明我们通过其他路径重新访问到了y，形成了一个环，因此当前路径不安全。如果y的状态为0，继续DFS探索。这种方法可以有效地利用之前的计算结果，避免重复工作，提高效率。

一旦一个节点被确认为安全节点，即其所有出边指向的节点都已被验证为安全或是终端节点，这意味着从这个节点出发不会形成任何可以回到自身的环。因此，在该节点的所有出边都验证完毕后，可以安全地将其状态设置为2，表示此节点及其所有出边都不会导致环的存在。此后再遇到这个节点时，可以直接使用这一信息，无需重复验证，从而优化整体的算法性能。

对于没有任何边的孤立节点，即其邻接列表为空的节点，在执行DFS时，既然没有出边去探索其他节点，这表示从该节点出发不可能到达任何其他节点，更不会形成环。因此，这样的节点在DFS处理过程中会被直接标记为安全节点（状态为2）。实际上，这类节点是最简单的安全节点案例。

在DFS过程中，将`c[x] = 1`即标记节点x为'正在访问'的状态，这是为了追踪当前DFS路径上的节点。当DFS访问到一个节点y，并且发现`c[y] = 1`时，说明y是在当前DFS路径上再次被访问到的，这表明从y到x之间形成了一个环。因此，这种标记帮助我们识别出图中的环结构，环的存在意味着从这些节点出发可能无法到达终端节点，从而不是安全的。