Medium

题目描述

有一个有向图，有 n 个节点，节点标号为 0 到 n - 1。图由一个下标从 0 开始的二维整数数组 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] 内。

解题思路

这道题要求找到有向图中的安全节点，即从该节点出发的所有路径都最终通向终端节点的节点。

核心思路： 一个节点是安全的，当且仅当它不在任何环中，且从它出发的所有路径都通向安全节点。我们可以用以下几种方法解决：

方法一：DFS + 颜色标记 使用三色标记法：白色（0）表示未访问，灰色（1）表示正在访问（在递归栈中），黑色（2）表示已完成访问。如果在DFS过程中遇到灰色节点，说明存在环，该路径上的所有节点都不安全。

方法二：拓扑排序（推荐） 将问题转化为拓扑排序。我们构建反向图，然后从所有出度为0的节点开始，逐步移除边，能被移除的节点就是安全节点。这种方法更直观，因为安全节点的特征就是最终能到达终端节点。

方法三：记忆化DFS 直接DFS判断每个节点是否安全，使用记忆化避免重复计算。

本题解采用拓扑排序方法，因为它思路清晰，代码简洁，且时间复杂度最优。

代码实现

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> reverseGraph(n);
        vector<int> outDegree(n, 0);
        
        // 构建反向图和计算出度
        for (int i = 0; i < n; i++) {
            outDegree[i] = graph[i].size();
            for (int neighbor : graph[i]) {
                reverseGraph[neighbor].push_back(i);
            }
        }
        
        // 将出度为0的节点加入队列
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (outDegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<bool> safe(n, false);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            safe[node] = true;
            
            // 处理反向图中的邻居
            for (int neighbor : reverseGraph[node]) {
                outDegree[neighbor]--;
                if (outDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        vector<int> result;
        for (int i = 0; i < n; i++) {
            if (safe[i]) {
                result.push_back(i);
            }
        }
        return result;
    }
};

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        reverse_graph = [[] for _ in range(n)]
        out_degree = [0] * n
        
        # 构建反向图和计算出度
        for i in range(n):
            out_degree[i] = len(graph[i])
            for neighbor in graph[i]:
                reverse_graph[neighbor].append(i)
        
        # 将出度为0的节点加入队列
        queue = []
        for i in range(n):
            if out_degree[i] == 0:
                queue.append(i)
        
        safe = [False] * n
        while queue:
            node = queue.pop(0)
            safe[node] = True
            
            # 处理反向图中的邻居
            for neighbor in reverse_graph[node]:
                out_degree[neighbor] -= 1
                if out_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        result = []
        for i in range(n):
            if safe[i]:
                result.append(i)
        return result

public class Solution {
    public IList<int> EventualSafeNodes(int[][] graph) {
        int n = graph.Length;
        List<int>[] reverseGraph = new List<int>[n];
        int[] outDegree = new int[n];
        
        // 初始化反向图
        for (int i = 0; i < n; i++) {
            reverseGraph[i] = new List<int>();
        }
        
        // 构建反向图和计算出度
        for (int i = 0; i < n; i++) {
            outDegree[i] = graph[i].Length;
            foreach (int neighbor in graph[i]) {
                reverseGraph[neighbor].Add(i);
            }
        }
        
        // 将出度为0的节点加入队列
        Queue<int> queue = new Queue<int>();
        for (int i = 0; i < n; i++) {
            if (outDegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        bool[] safe = new bool[n];
        while (queue.Count > 0) {
            int node = queue.Dequeue();
            safe[node] = true;
            
            // 处理反向图中的邻居
            foreach (int neighbor in reverseGraph[node]) {
                outDegree[neighbor]--;
                if (outDegree[neighbor] == 0) {
                    queue.Enqueue(neighbor);
                }
            }
        }
        
        List<int> result = new List<int>();
        for (int i = 0; i < n; i++) {
            if (safe[i]) {
                result.Add(i);
            }
        }
        return result;
    }
}

var eventualSafeNodes = function(graph) {
    const n = graph.length;
    const reverseGraph = Array.from({length: n}, () => []);
    const outDegree = new Array(n).fill(0);
    
    // 构建反向图和计算出度
    for (let i = 0; i < n; i++) {
        outDegree[i] = graph[i].length;
        for (const neighbor of graph[i]) {
            reverseGraph[neighbor].push(i);
        }
    }
    
    // 将出度为0的节点加入队列
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (outDegree[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(V + E)，其中 V 是节点数，E 是边数
空间复杂度O(V + E)，用于存储反向图和辅助数组

相关题目