# 0802. Find Eventual Safe States
###### tags: `Leetcode` `Medium` `DFS` `DFS-color`
Link: https://leetcode.com/problems/find-eventual-safe-states/
## 思路 $O(N)$ $O(1)$
unsafe node有两种情况：
- 有一条路径能到另一个unsafe node
- 有一条路径能连到自己

因此用颜色标记法，0代表还没访问过，1代表safe node，2代表unsafe node
对于每一个node做dfs，检查从它开始的所有路径，如果有连到自己/unsafe node的，就直接return false，不加进答案中
## Code

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> ans = new ArrayList<>();
        int[] colors = new int[graph.length];
        for(int i = 0;i < graph.length;i++){
            if(dfs(colors, i, graph)){
                ans.add(i);
            }
        }
        return ans;
    }
    private boolean dfs(int[] colors, int node, int[][] graph){
        //color = 0 have not been visited
        //color = 1 safe node
        //color = 2 unsafe node
        if(colors[node]!=0) return colors[node]==1;
        colors[node] = 2;
        for(int neigh:graph[node]){
            if(!dfs(colors, neigh, graph)) return false;
        }
        colors[node] = 1;
        return true;
    }
}