找到最终的安全状态 深搜

传送门

　　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;
    }
}