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

一【标题类别】

• 图
  

二【标题难度】

• 中等
  

三【标题编号】

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

四【标题描述】

• 有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph体现， graph是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph中的每个节点都有一条边。
  
• 如果一个节点没有连出的有向边，则该节点是 终端节点 。如果从该节点开始的全部可能路径都通向 终端节点 ，则该节点为 安全节点 。
  
• 返回一个由图中全部 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 分列。
  

五【标题示例】

• 示例 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                            =                            =                            g                            r                            a                            p                            h                            .                            l                            e                            n                            g                            t                            h                                  n == graph.length                     n==graph.length
  
•                                         1                            <                            =                            n                            <                            =                            1                                       0                               4                                            1 <= n <= 10^4                     1<=n<=104
  
•                                         0                            <                            =                            g                            r                            a                            p                            h                            [                            i                            ]                            .                            l                            e                            n                            g                            t                            h                            <                            =                            n                                  0 <= graph.length <= n                     0<=graph.length<=n
  
•                                         0                            <                            =                            g                            r                            a                            p                            h                            [                            i                            ]                            [                            j                            ]                            <                            =                            n                            −                            1                                  0 <= graph[j] <= n - 1                     0<=graph[j]<=n−1
  
•                                         g                            r                            a                            p                            h                            [                            i                            ]                                  graph                     graph 按严酷递增次序分列。
  
• 图中可能包含自环。
  
• 图中边的数目在范围                                         [                            1                            ,                            4                            ∗                            1                                       0                               4                                      ]                                  [1, 4 * 10^4]                     [1,4∗104] 内。
  

七【解题思路】

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

八【时空频度】

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

九【代码实现】

• Java语言版
  

1. class Solution {
2.     public List<Integer> eventualSafeNodes(int[][] graph) {
3.         // 图中节点的个数
4.         int n = graph.length;
5.         // 用来存储反向图
6.         List<List<Integer>> reverseGraph = new ArrayList<>();
7.         for (int i = 0; i < n; i++) {
8.             reverseGraph.add(new ArrayList<>());
9.         }
10.         // 每个节点的出度
11.         int[] outDegree = new int[n];
12.         // 构建反向图和出度数组
13.         for (int i = 0; i < n; i++) {
14.             outDegree[i] = graph[i].length;
15.             for (int neighbor : graph[i]) {
16.                 reverseGraph.get(neighbor).add(i);
17.             }
18.         }
19.         // 初始化队列，将所有终端节点（出度为0的节点）加入队列
20.         Queue<Integer> queue = new LinkedList<>();
21.         for (int i = 0; i < n; i++) {
22.             if (outDegree[i] == 0) {
23.                 queue.offer(i);
24.             }
25.         }
26.         // 用集合存储安全节点
27.         Set<Integer> safeNodes = new HashSet<>(queue);
28.         // 逆向拓扑排序
29.         while (!queue.isEmpty()) {
30.             int node = queue.poll();
31.             for (int neighbor : reverseGraph.get(node)) {
32.                 outDegree[neighbor]--;
33.                 if (outDegree[neighbor] == 0) {
34.                     safeNodes.add(neighbor);
35.                     queue.offer(neighbor);
36.                 }
37.             }
38.         }
39.         // 返回安全节点的升序列表
40.         List<Integer> res = new ArrayList<>(safeNodes);
41.         Collections.sort(res);
42.         return res;
43.     }
44. }

复制代码

• Python语言版
  

1. class Solution:
2.     def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
3.         # 图中节点的个数
4.         n = len(graph)
5.         # 用来存储反向图
6.         reverse_graph = defaultdict(list)
7.         # 每个节点的出度
8.         out_degree = [0] * n
9.         # 构建反向图和出度数组
10.         for i, neighboors in enumerate(graph):
11.             out_degree[i] = len(neighboors)
12.             for neighboor in neighboors:
13.                 reverse_graph[neighboor].append(i)
14.         # 初始化队列，将所有终端节点（出度为0的节点）加入队列
15.         queue = deque(i for i in range(n) if out_degree[i] == 0)
16.         # 用集合存储安全节点
17.         safe_nodes = set(queue)
18.         # 逆向拓扑排序
19.         while queue:
20.             node = queue.popleft()
21.             for neighboor in reverse_graph[node]:
22.                 out_degree[neighboor] -= 1
23.                 if out_degree[neighboor] == 0:
24.                     safe_nodes.add(neighboor)
25.                     queue.append(neighboor)
26.         # 返回安全节点的升序列表
27.         return sorted(safe_nodes)

复制代码

• C++语言版
  

1. class Solution {
2. public:
3.     vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
4.         // 图中节点的个数
5.         int n = graph.size();
6.         // 用来存储反向图
7.         vector<vector<int>> reverseGraph(n);
8.         // 每个节点的出度
9.         vector<int> outDegree(n, 0);
10.         // 构建反向图和出度数组
11.         for (int i = 0; i < n; i++) {
12.             outDegree[i] = graph[i].size();
13.             for (int neighbor : graph[i]) {
14.                 reverseGraph[neighbor].push_back(i);
15.             }
16.         }
17.         // 初始化队列，将所有终端节点（出度为0的节点）加入队列
18.         queue<int> q;
19.         // 用集合存储安全节点
20.         unordered_set<int> safeNodes;
21.         for (int i = 0; i < n; i++) {
22.             if (outDegree[i] == 0) {
23.                 q.push(i);
24.                 safeNodes.insert(i);
25.             }
26.         }
27.         // 逆向拓扑排序
28.         while (!q.empty()) {
29.             int node = q.front();
30.             q.pop();
31.             for (int neighbor : reverseGraph[node]) {
32.                 outDegree[neighbor]--;
33.                 if (outDegree[neighbor] == 0) {
34.                     safeNodes.insert(neighbor);
35.                     q.push(neighbor);
36.                 }
37.             }
38.         }
39.         // 返回安全节点的升序列表
40.         vector<int> res(safeNodes.begin(), safeNodes.end());
41.         sort(res.begin(), res.end());
42.         return res;
43.     }
44. };

复制代码

十【提交结果】

• Java语言版
  
  
  
  
• Python语言版
  
  
  
  
• C++语言版
  
  
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。