找到最终的安全状态

题目:找到最终的安全状态

对于一个起始节点,如果从该节点出发,无论每一步选择沿哪条有向边行走,最后必然在有限步内到达终点,则将该起始节点称作是 安全的。

返回一个由图中所有安全节点,节点应当按 升序 排列。

示例 1:

Illustration of graph

输入:graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]

 

题解

  1. 将所有边逆序,得到逆序图
  2. 在逆序图中,寻找拓扑排序。
  3. 所有拓扑排序的节点都是安全节点
class Solution {
        public List<Integer> eventualSafeNodes(int[][] graph) {
            Queue<Integer> queue=new ArrayDeque<>();
            int book[]=new int[graph.length];
            List<Integer> map[]=new List[graph.length];
            List<Integer> res=new ArrayList<>();

            for(int i=0;i<graph[i].length;i++)
            {
                for(int j=0;j<graph.length;j++)
                {
                    if(map[graph[i][j]]==null) map[graph[i][j]]=new ArrayList<>();
                    map[graph[i][j]].add(i);
                    book[i]++;
                }
            }

            for(int i=0;i<book.length;i++){
                if(book[i]==0){
                    queue.add(i);
                }
            }

            while (!queue.isEmpty())
            {
                int temp=queue.poll();
                res.add(temp);

                if(map[temp]!=null && map[temp].size()>0)
                {
                    for(int i=0;i<map[temp].size();i++)
                    {
                        if(--book[map[temp].get(i)]==0)
                            queue.add(map[temp].get(i));
                    }
                }
            }
            Collections.sort(res);
            return res;
        }
    }

 

更多文章请关注《万象专栏》

本栏目由《康祺惠购APP》独家赞助