LeetCode 802. 找到最终的安全状态

题目描述
有一个有向图，包含 n 个节点，节点编号从 0 到 n-1。图用一个节点列表表示，其中 graph[i] 是节点 i 的所有有向出边指向的节点列表。我们定义：一个节点是“安全”的，如果从该节点出发，无论每一步选择哪条有向边，最终都一定会到达一个出度为 0 的节点（即没有出边的节点，也称为“终端节点”），或者进入一个环，但该环上的所有节点也都满足“安全”的定义（实际上，这意味着这个环不能是“不安全”的，即不会进入一个包含非安全节点的环）。更直观地说，安全节点是指那些所有可能的路径都不会进入一个环（除非这个环本身所有节点都是安全的，但根据定义，不安全的环会导致节点不安全）。实际上，题目可以简化为：找出所有不会进入环的节点（即从该节点出发的所有路径最终都能到达终端节点）。你需要返回一个升序排列的安全节点列表。

示例 1
输入：graph = [[1,2],[2,3],[3,4],[4],[]]
输出：[0,1,2,3,4]
解释：

• 节点 4 是终端节点，因为它没有出边。
• 节点 3 指向节点 4，所以安全。
• 节点 2 指向节点 3，所以安全。
• 节点 1 指向节点 2，所以安全。
• 节点 0 指向节点 1 和 2，都安全，所以安全。

示例 2
输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]
解释：

• 节点 4 是终端节点，安全。
• 节点 3 指向节点 0 和 4。从节点 3 出发，如果走到节点 0，节点 0 指向节点 1,2,3,4，其中又可能回到节点 3，形成环，且这个环不满足安全（因为环上节点 0,3 等可能走向其他节点，但最终会进入环且无法到达终端节点），所以节点 3 不安全。
• 类似地，节点 0,1,2 也不安全。只有节点 4 安全。

题目理解
这个问题可以转化为：在有向图中，找出所有从该节点出发不会进入环的节点。这里的“环”指的是任何导致路径无法终止于终端节点的环。因为如果进入一个环，且这个环上任意节点有出边指向终端节点，那么实际上路径可能脱离环到达终端，但根据定义，如果存在一条路径永远在环上走，那就不安全。但更严谨地说，安全节点等价于：从该节点出发的所有路径最终都能到达终端节点。这等价于：该节点不在任何一个环上，且从该节点出发不会到达任何一个环（除了可能由安全节点构成的环，但安全节点构成的环其实不可能存在，因为如果所有节点安全，则它们最终都指向终端节点，不会形成环）。所以我们可以简化为：找出所有不在环中，且不会到达环的节点。实际上，这可以通过“拓扑排序”的变种来解决。

解题思路
常规想法是检测环，但我们需要找出所有安全节点。一个高效的方法是：将图的所有边反向，然后从所有终端节点（在反向图中就是入度为 0 的节点）开始进行拓扑排序。
为什么？

1. 原图中安全节点的定义是：所有路径最终到达终端节点。
2. 如果我们把图反向，那么从终端节点出发，在反向图中能到达的节点，就是原图中能到达终端节点的节点，也就是安全节点。
3. 在反向图中，终端节点变成入度为 0 的节点（因为原图中它们出度为 0，反向后就入度为 0）。我们可以从这些节点开始做拓扑排序，过程类似于 BFS，每次从队列中取出一个节点，将它标记为安全，然后遍历它的所有邻居（在反向图中的邻居，即原图中指向它的节点），将邻居的入度减 1，如果邻居入度变为 0，则加入队列。
4. 最终，所有入度能变为 0 的节点就是安全节点。

另一种思路是直接使用 DFS 加状态标记，每个节点有三种状态：未访问（0），访问中（1，表示在当前 DFS 路径中），已安全（2）。如果在 DFS 过程中遇到状态 1 的节点，说明有环，当前路径上的节点都不安全。如果所有出边指向的节点都是安全的，则当前节点安全。

这里我选择讲解反向图拓扑排序的方法，因为它更直观且高效。

详细步骤

1. 构建反向图：
   给定原图 graph，其中 graph[i] 是节点 i 指向的邻居列表。
   我们创建一个新的图 reverseGraph，长度为 n，reverseGraph[i] 是一个列表，存放所有指向节点 i 的节点。
   同时，我们记录每个节点在反向图中的入度（即原图中的出度）。注意：在反向图的拓扑排序中，我们实际上需要的是节点在反向图中的入度。但更方便的做法是：我们直接使用原图的出度信息，但反向图是为了方便从终端节点开始 BFS。

   更简单的方法：

   • 我们不需要显式构建反向图，只需要在 BFS 过程中，对于每个节点，我们能快速找到哪些节点指向它。所以我们可以提前构建一个“入边”列表 inEdges，其中 inEdges[i] 是一个列表，存放所有指向节点 i 的节点。
   • 同时，我们记录每个节点的出度 outDegree[i]，即原图中节点 i 的出边数量。
   • 在拓扑排序中，我们使用队列，初始化时将所有出度为 0 的节点（即终端节点）入队。

   注意：这里的拓扑排序是在原图上进行的，但排序方向是“从终端节点反向传播安全状态”。实际上，这等价于在反向图上做拓扑排序。

2. 算法过程：
   a. 初始化：

   • n = graph.length
   • outDegree = new int[n]，其中 outDegree[i] = graph[i].size()
   • inEdges = new List[n]，其中 inEdges[i] 存放所有指向 i 的节点。遍历原图，对于每条边 i -> j，将 i 加入 inEdges[j]。
   • 队列 queue，将所有 outDegree[i] == 0 的节点 i 入队。

   b. BFS 拓扑排序：

   • 当队列不为空时，取出队首节点 u。此时节点 u 是安全的（因为出度为 0，或者它的所有出边指向的节点都已经安全）。
   • 遍历所有指向 u 的节点 v（即 inEdges[u] 中的节点），将 v 的出度减 1（因为从 v 到 u 的这条边已经考虑过了，相当于在反向图中，u 被移除，导致 v 的入度减 1）。
   • 如果 v 的出度减为 0，则将 v 入队。
   • 重复直到队列为空。

   c. 收集结果：

   • 所有在过程中出队的节点都是安全节点。因为出队顺序不一定，最后需要排序。实际上，因为节点编号 0 到 n-1，我们可以直接遍历，如果最终出度变为 0 的节点就是安全的。注意：在 BFS 过程中，当一个节点出度减为 0 时才入队，并且出队时它一定是安全的。所以我们可以记录一个 safe 布尔数组，节点出队时标记为 true。
   • 最后，遍历 0 到 n-1，将 safe[i] 为 true 的节点加入结果列表，自然就是升序。

3. 正确性说明：
   这个算法本质上是将原图视为一个有向图，安全节点就是所有能到达终端节点且不会进入环的节点。通过从终端节点反向 BFS，我们逐步将安全状态向前传递。如果一个节点的所有出边都指向安全节点，那么它也是安全的。在算法中，当我们移除一个安全节点 u 时，对于所有指向 u 的节点 v，相当于 v 少了一个不安全的出边（因为 u 是安全的）。当 v 的所有出边都指向安全节点时，v 的出度变为 0，然后被加入队列。这保证了最终所有安全节点都会被标记。

4. 复杂度分析：

   • 时间复杂度：O(n + e)，其中 n 是节点数，e 是边数（即 graph 中所有列表长度之和）。构建入边列表需要 O(n + e)，BFS 每个节点和边访问一次。
   • 空间复杂度：O(n + e)，存储入边列表和队列等。

示例演示
以示例 2 为例：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

• n=5, 计算 outDegree: [4,2,2,2,0]
• 构建 inEdges:
  0: [3]
  1: [0,1]
  2: [0,1]
  3: [0,2]
  4: [0,1,2,3]
• 初始队列：节点 4（outDegree[4]=0）
• BFS:
  取出 4，遍历 inEdges[4]=[0,1,2,3]，将它们的 outDegree 减 1：
  outDegree[0]=3, outDegree[1]=1, outDegree[2]=1, outDegree[3]=1
  没有变为 0 的节点，队列空。
• 最终 outDegree 不为 0 的节点是 0,1,2,3，只有节点 4 的 outDegree=0，所以安全节点只有 [4]。

代码框架（Java）

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] outDegree = new int[n];
        List<Integer>[] inEdges = new List[n];
        for (int i = 0; i < n; i++) {
            inEdges[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            outDegree[i] = graph[i].length;
            for (int j : graph[i]) {
                inEdges[j].add(i);
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (outDegree[i] == 0) {
                queue.offer(i);
            }
        }
        boolean[] safe = new boolean[n];
        while (!queue.isEmpty()) {
            int u = queue.poll();
            safe[u] = true;
            for (int v : inEdges[u]) {
                outDegree[v]--;
                if (outDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (safe[i]) {
                ans.add(i);
            }
        }
        return ans;
    }
}

总结
本题通过反向图拓扑排序，巧妙地将“安全节点”问题转化为从终端节点开始的拓扑排序问题。核心思想是：安全节点就是那些所有出边都指向安全节点的节点，终端节点是初始安全节点，然后安全状态逆向传播。这种方法避免了深搜可能遇到的环检测问题，且时间效率很高。