• 周二. 8月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

找到最终的安全状态 深搜

admin

11月 28, 2021

传送门

  https://leetcode-cn.com/problems/find-eventual-safe-states/

题意

思路

AC代码

import java.util.ArrayList;
import java.util.List;

class Solution {



    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        List<Integer> res = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(dfs(graph,color,i)){
                res.add(i);
            }
        }
        return res;
    }

    private boolean dfs(int[][] graph, int[] color, int x) {
        if(color[x] == 1){
            return false;
        }else if(color[x] == 2){
            return true;
        }
        color[x] = 1;
        for (int y : graph[x]) {
            if(dfs(graph,color,y) == false){
                return false;
            }
        }
        color[x] = 2;
        return true;
    }
}

 

  

 

  

  

一点一点积累,一点一点蜕变!

发表评论

您的电子邮箱地址不会被公开。