文章目录
一【题目类别】
- 图
二【题目难度】
- 中等
三【题目编号】
- 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 = = g r a p h . l e n g t h n == graph.length n==graph.length1 < = n < = 1 0 4 1 <= n <= 10^4 1<=n<=1040 < = g r a p h [ i ] . l e n g t h < = n 0 <= graph[i].length <= n 0<=graph[i].length<=n0 < = g r a p h [ i ] [ j ] < = n − 1 0 <= graph[i][j] <= n - 1 0<=graph[i][j]<=n−1g r a p h [ i ] graph[i] graph[i] 按严格递增顺序排列。- 图中可能包含自环。
- 图中边的数目在范围 [ 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语言版
classSolution{publicList<Integer>eventualSafeNodes(int[][] graph){// 图中节点的个数int n = graph.length;// 用来存储反向图List<List<Integer>> reverseGraph =newArrayList<>();for(int i =0; i < n; i++){
reverseGraph.add(newArrayList<>());}// 每个节点的出度int[] outDegree =newint[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 =newLinkedList<>();for(int i =0; i < n; i++){if(outDegree[i]==0){
queue.offer(i);}}// 用集合存储安全节点Set<Integer> safeNodes =newHashSet<>(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 =newArrayList<>(safeNodes);Collections.sort(res);return res;}}
- Python语言版
classSolution:defeventualSafeNodes(self, graph: List[List[int]])-> List[int]:# 图中节点的个数
n =len(graph)# 用来存储反向图
reverse_graph = defaultdict(list)# 每个节点的出度
out_degree =[0]* n
# 构建反向图和出度数组for i, neighboors inenumerate(graph):
out_degree[i]=len(neighboors)for neighboor in neighboors:
reverse_graph[neighboor].append(i)# 初始化队列，将所有终端节点（出度为0的节点）加入队列
queue = deque(i for i inrange(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)# 返回安全节点的升序列表returnsorted(safe_nodes)
- C++语言版
classSolution{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;}};
十【提交结果】
- Java语言版
- Python语言版
- C++语言版
本文转载自: https://blog.csdn.net/IronmanJay/article/details/143425349
版权归原作者 IronmanJay 所有， 如有侵权，请联系我们删除。
版权归原作者 IronmanJay 所有， 如有侵权，请联系我们删除。