802. Find Eventual Safe States

There are two methods to check whether a circle exists in a directed graph:

1. Topological sort
2. Graph coloring

Here, we solve this problem through graph coloring. About graph coloring, we can refer to 785. Is Graph Bipartite?. We use a array color to mark the node of graph:

• 0 means the node has not been visited
• 1 means the node is not safe
• 2 means the node is safe

public List<Integer> eventualSafeNodes(int[][] graph) {
    List<Integer> resultList = new ArrayList<Integer>();
    int color[] = new int[graph.length];
    for(int i = 0; i < graph.length; i++) {
        if( traverse(i, graph, color) )
            resultList.add(i);
    }
    return resultList;
}

public boolean traverse(int index, int[][] graph, int[] color) {
    if( color[index] > 0 )
        return color[index] == 2;

    color[index] = 1;
    for(int i = 0; i < graph[index].length; i++) {
        if( color[graph[index][i]] == 2 )
            continue;

        else if( color[graph[index][i]] == 1 || !traverse(graph[index][i], graph, color) )
            return false;
    }
    color[index] = 2;
    return true;
}