802.找到最终的安全状态

在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。

对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。

返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。

提示：

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].length <= n
• graph[i] 按严格递增顺序排列。
• 图中可能包含自环。
• 图中边的数目在范围 [1, 4 * 104] 内。

思路：深度遍历 + 三色标记
1.当一个节点位于环内，则这个节点不安全
2.三色标记：0未访问/1位于递归栈中or不安全/2安全节点

当我们首次访问一个节点时，将其标记为灰色，并继续搜索与其相连的节点。

如果在搜索过程中遇到了一个灰色节点，则说明找到了一个环，此时退出搜索，栈中的节点仍保持为灰色，这一做法可以将「找到了环」这一信息传递到栈中的所有节点上。

如果搜索过程中没有遇到灰色节点，则说明没有遇到环，那么递归返回前，我们将其标记由灰色改为黑色，即表示它是一个安全的节点。

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

    private boolean isSafe(int[][] graph , int[] color , int p){
        if(color[p] > 0){    //当前节点已访问过
            return color[p] == 2;
        }
        color[p] = 1;        //第一次访问当前节点
        for(int q : graph[p]){    //深度优先遍历
            if(!isSafe(graph , color , q)){    //访问到不安全节点，说明当前节点在环内
                return false;
            }
        }
        color[p] = 2;        //当前节点的所有边都安全，标记当前节点为安全
        return true;

    }
}