802. Find Eventual Safe States

Link

Solution

這題找loop的方法蠻特別的將已經visited都先設成unsafe，然後之後檢查是否traverse到unsafe node。

此時的unsafe node包含兩種狀況。 一個是之前確定的unsafe node，另一個是本次traversal時已經遇過的點。

    public List<Integer> eventualSafeNodes(int[][] graph) {
        int N = graph.length;
        int[] color = new int[N];
        //0: unvisited
        //1: safe
        //2: unsafe
        List<Integer> ret = new LinkedList<>();
        for(int i = 0; i < N; i++){
            if(dfs(graph, color, 2, i)) ret.add(i);
        }
        return ret;
    }
    
    public boolean dfs(int[][] graph, int[] color, int newColor, int i){
        
        if(color[i] != 0) return color[i] == 1;
        
        //check if has a loop
        color[i] = 2;
        for(int adj : graph[i]){
            if(!dfs(graph, color, 2, adj)) return false;
        }
        color[i] = 1;
        return true;
    }