0802. 找到最终的安全状态【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 拓扑排序

1. 📝 题目描述

• leetcode

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

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

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

---

示例 1：

输入：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^4
• 0 <= graph[i].length <= n
• 0 <= graph[i][j] <= n - 1
• graph[i] 按严格递增顺序排列。
• 图中可能包含自环。
• 图中边的数目在范围 [1, 4 * 10^4] 内。

2. 🎯 s.1 - 拓扑排序

c

int* eventualSafeNodes(int** graph, int graphSize, int* graphColSize, int* returnSize) {
    int n = graphSize;
    int* outDeg = (int*)calloc(n, sizeof(int));
    int** rg = (int**)malloc(sizeof(int*) * n);
    int* rgSize = (int*)calloc(n, sizeof(int));
    int* rgCap = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) { rg[i] = (int*)malloc(sizeof(int) * 4); rgCap[i] = 4; }
    for (int i = 0; i < n; i++) {
        outDeg[i] = graphColSize[i];
        for (int j = 0; j < graphColSize[i]; j++) {
            int v = graph[i][j];
            if (rgSize[v] == rgCap[v]) { rgCap[v] *= 2; rg[v] = realloc(rg[v], sizeof(int) * rgCap[v]); }
            rg[v][rgSize[v]++] = i;
        }
    }
    int* queue = (int*)malloc(sizeof(int) * n);
    int front = 0, back = 0;
    bool* safe = (bool*)calloc(n, sizeof(bool));
    for (int i = 0; i < n; i++) if (outDeg[i] == 0) queue[back++] = i;
    while (front < back) {
        int u = queue[front++];
        safe[u] = true;
        for (int i = 0; i < rgSize[u]; i++) {
            int v = rg[u][i];
            if (--outDeg[v] == 0) queue[back++] = v;
        }
    }
    int* res = (int*)malloc(sizeof(int) * n);
    *returnSize = 0;
    for (int i = 0; i < n; i++) if (safe[i]) res[(*returnSize)++] = i;
    for (int i = 0; i < n; i++) free(rg[i]);
    free(rg); free(rgSize); free(rgCap); free(outDeg); free(queue); free(safe);
    return res;
}

js

/**
 * @param {number[][]} graph
 * @return {number[]}
 */
var eventualSafeNodes = function (graph) {
  const n = graph.length
  const rg = Array.from({ length: n }, () => [])
  const outDeg = new Array(n).fill(0)
  for (let i = 0; i < n; i++) {
    for (const j of graph[i]) rg[j].push(i)
    outDeg[i] = graph[i].length
  }
  const queue = []
  for (let i = 0; i < n; i++) if (outDeg[i] === 0) queue.push(i)
  const safe = new Array(n).fill(false)
  while (queue.length) {
    const u = queue.shift()
    safe[u] = true
    for (const v of rg[u]) {
      if (--outDeg[v] === 0) queue.push(v)
    }
  }
  const res = []
  for (let i = 0; i < n; i++) if (safe[i]) res.push(i)
  return res
}

py

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        from collections import deque
        n = len(graph)
        rg = [[] for _ in range(n)]
        out_deg = [0] * n
        for i, neis in enumerate(graph):
            out_deg[i] = len(neis)
            for j in neis:
                rg[j].append(i)
        queue = deque(i for i in range(n) if out_deg[i] == 0)
        safe = [False] * n
        while queue:
            u = queue.popleft()
            safe[u] = True
            for v in rg[u]:
                out_deg[v] -= 1
                if out_deg[v] == 0:
                    queue.append(v)
        return [i for i in range(n) if safe[i]]

• 时间复杂度：$O(V+E)$，其中 V 是节点数，E 是边数
• 空间复杂度：$O(V+E)$

算法思路：

• 构建反向图，统计每个节点的出度
• 出度为 0 的节点（终端节点）一定是安全的，从这些节点开始 BFS
• 将安全节点的前驱出度减 1，出度变为 0 的节点也是安全的