leetcode 802. Find Eventual Safe States_802 leetcode java

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less thanK steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output:[2,4,5,6]
Here is a diagram of the above graph.

我们可以使用染色法来解决这道题：
在这里我给出三种颜色。
0:代表没有颜色
1:safe颜色
2:unsafe不安全颜色
递归的更新每个节点的颜色，就OK了。

class Solution {
   public  List<Integer> eventualSafeNodes(int[][] graph) {
        // 0: 没有 color
        // 1 : safe 
        // 2 : unsafe

        // 默认都是 没有颜色的
        int[] colors = new int[graph.length];
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) {
            if (dfs(graph, i, colors)) {
                res.add(i);
            }
        }
        return res;

    }
    public  boolean dfs(int[][] graph, int color, int[] colors) {
        // 如果 这点已经有颜色了
        if (colors[color] != 0) {
            return colors[color] == 1; // 看他是否 safe
        }
        // 先把这点 置为不安全，只有他的后继节点都安全， 才把他置为安全
        colors[color] = 2;
        for (int color_next : graph[color]) {
            if (!dfs(graph, color_next, colors)) {
                return false;
            }
        }
        colors[color] = 1;
        return true;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34