【LeetCode每日一题】——802.找到最终的安全状态

一【题目类别】

• 图

二【题目难度】

• 中等

三【题目编号】

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

四【题目描述】

• 有一个有 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\ast 10^4]$ 内。

七【解题思路】

• 利用拓扑排序的思想解决该问题
• 我们首先构建一个反向图，即假如之前i -> j，那么反向图就变为j -> i，反向图的目的是用来后续计算出度来找到终端节点
• 同时构建原图的出度数组，后续就会用该数组来找到安全节点
• 然后将得到的所有终端节点都入队列，后续操作该队列即可得到所有终端节点
• 然后将得到的安全节点（所有终端节点都是安全节点）保存到集合中
• 然后通过逆向拓扑排序计算得到安全节点：
  • 首先从队列中取出一个安全节点
  • 然后查看它的邻接节点
    • 然后将邻接节点的出度减1
    • 如果此时出度为0，那么说明其为安全节点，将其入队列和集合中
• 具体细节可以参考下面的代码
• 最后返回结果即可

八【时空频度】

• 时间复杂度：$O(m+n)$，$m$为图的节点数，$n$为图的边数
• 空间复杂度：$O(m+n)$，$m$为图的节点数，$n$为图的边数

九【代码实现】

1. Java语言版

class Solution {public List<Integer> eventualSafeNodes(int[][] graph) {// 图中节点的个数int n = graph.length;// 用来存储反向图List<List<Integer>> reverseGraph = new ArrayList<>();for (int i = 0; i < n; i++) {reverseGraph.add(new ArrayList<>());}// 每个节点的出度int[] outDegree = new int[n];// 构建反向图和出度数组for (int i = 0; i < n; i++) {outDegree[i] = graph[i].length;for (int neighbor : graph[i]) {reverseGraph.get(neighbor).add(i);}}// 初始化队列，将所有终端节点（出度为0的节点）加入队列Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < n; i++) {if (outDegree[i] == 0) {queue.offer(i);}}// 用集合存储安全节点Set<Integer> safeNodes = new HashSet<>(queue);// 逆向拓扑排序while (!queue.isEmpty()) {int node = queue.poll();for (int neighbor : reverseGraph.get(node)) {outDegree[neighbor]--;if (outDegree[neighbor] == 0) {safeNodes.add(neighbor);queue.offer(neighbor);}}}// 返回安全节点的升序列表List<Integer> res = new ArrayList<>(safeNodes);Collections.sort(res);return res;}
}

2. Python语言版

class Solution:def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:# 图中节点的个数n = len(graph)# 用来存储反向图reverse_graph = defaultdict(list)# 每个节点的出度out_degree = [0] * n# 构建反向图和出度数组for i, neighboors in enumerate(graph):out_degree[i] = len(neighboors)for neighboor in neighboors:reverse_graph[neighboor].append(i)# 初始化队列，将所有终端节点（出度为0的节点）加入队列queue = deque(i for i in range(n) if out_degree[i] == 0)# 用集合存储安全节点safe_nodes = set(queue)# 逆向拓扑排序while queue:node = queue.popleft()for neighboor in reverse_graph[node]:out_degree[neighboor] -= 1if out_degree[neighboor] == 0:safe_nodes.add(neighboor)queue.append(neighboor)# 返回安全节点的升序列表return sorted(safe_nodes)

3. C++语言版

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;// 用集合存储安全节点unordered_set<int> safeNodes;for (int i = 0; i < n; i++) {if (outDegree[i] == 0) {q.push(i);safeNodes.insert(i);}}// 逆向拓扑排序while (!q.empty()) {int node = q.front();q.pop();for (int neighbor : reverseGraph[node]) {outDegree[neighbor]--;if (outDegree[neighbor] == 0) {safeNodes.insert(neighbor);q.push(neighbor);}}}// 返回安全节点的升序列表vector<int> res(safeNodes.begin(), safeNodes.end());sort(res.begin(), res.end());return res;}
};

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版