802.找到最终的安全状态

发表于： 分类于：
字数： 1428 阅读：≈ 3分钟

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

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

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

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

思路

基本思想

按照题目描述，要找到所有的安全节点，而终端节点一定是安全节点，然后从终端节点向前推，从某个节点出发，只能到达终端节点，这种的节点称为安全节点

然后在这个基础上继续向前推，从某个节点出发，只能够到达上面提到的安全节点（包括安全节点和终端节点）,这种节点一定是安全节点

按照上面的分析过程，一个节点出发的所有路径上遍历的所有节点，一定要都是安全节点，那么这个节点才算是安全节点，所以可以看成是一个从终端节点回退的过程，知道了终端节点，才知道一步到达终端节点的所有安全节点node1，之后才知道一步到达node1，再一步到达终端节点的所有node2。这样一步一步的回退，最终能够找到所有的安全节点

上面的分析过程，如果反过来，我们将所有的终端节点当起点，node1的上一步节点全是终端节点，node2的上一步节点全是node1。而终端节点的入度为0，删除所有的终端节点后，node1节点的入度又为0。按照这样的思想，也就是从终端节点出发，不断地进行拓扑排序，找到所有入度为0的节点，然后减小所有邻接节点的入度，再找到所有入度为零的节点。。。以此类推就能找到所有安全节点

前提是需要根据题目中给的图将其进行逆转，A->B变成B->A，并且需要统计所有节点的入度，便于进行拓扑排序

核心就是明白，反向之后，安全节点的上一步节点一定是安全节点，最终递推到终端节点，其入度为零，利用拓扑排序就可以找到所有的安全节点

执行流程

  1. 图的反向，需要先建立一个List<List>，并且需要初始化n个List放到图中，因为后期需要按照索引获取并构造节点列表，代码为：

    1
2
3
4
5

     //由于节点出现的随机性，所以要先将内部的List构造好后期直接取
//而不是临时新建
for(int i=0;i<graph.length;++i){
    inverseGraph.add(new ArrayList<>());
}

  2. 统计每一个节点的入度，当前节点i的入度就是当前graph[i]的长度

  3. 进行拓扑排序，统计所有入度为0的节点，也就是安全节点

  4. 按照要求将安全节点排序并返回

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    //将给定的图反向，然后直接应用拓扑排序
    public List<Integer> eventualSafeNodes(int[][] graph) {
        //构造一个反向图，并记录每个点的入度
        List<List<Integer>> inverseGraph=new ArrayList<>();
        List<Integer> res=new ArrayList<>();
        //由于节点出现的随机性，所以要先将内部的List构造好后期直接取
        //而不是临时新建
        for(int i=0;i<graph.length;++i){
            inverseGraph.add(new ArrayList<>());
        }
        int[] inNode=new int[graph.length];
        //遍历正向图，构造反向图
        for(int i=0;i<graph.length;++i){
            for(int j=0;j<graph[i].length;++j){
                int node=graph[i][j];
                inverseGraph.get(node).add(i);
            }
            //当前反向图中节点i的入度
            inNode[i]=graph[i].length;
        }
        //开始拓扑排序
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<inNode.length;++i){
            //当前节点的入度为0，当前节点是安全节点
            if(inNode[i]==0){
                queue.add(i);
                res.add(i);
            }
        }
        while(queue.size()>0){
            int node=queue.poll();
            //当前节点的所有邻接节点的入度减-1
            for(Integer next:inverseGraph.get(node)){
                inNode[next]--;
                if(inNode[next]==0){
                    queue.add(next);
                    res.add(next);
                }
            }
        }
        //对列为空时找到了所有的安全节点，进行排序后返回
        Collections.sort(res,(a,b)->a-b);
        return res;
    }
}

总结

主要是完成问题的转换，从终端节点获取安全节点的递推过程类似于拓扑排序的过程，所以将图进行反向，然后利用拓扑排序求出所有的安全节点，同时为了便于后面直接根据索引获取并构造邻接节点列表，在开始就填充了n个list