找到最终的安全状态
题目:找到最终的安全状态
对于一个起始节点,如果从该节点出发,无论每一步选择沿哪条有向边行走,最后必然在有限步内到达终点,则将该起始节点称作是 安全的。
返回一个由图中所有安全节点,节点应当按 升序 排列。
示例 1:
输入:graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]
题解
- 将所有边逆序,得到逆序图
- 在逆序图中,寻找拓扑排序。
- 所有拓扑排序的节点都是安全节点
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;
}
}