802 Find Eventual Safe States

802. Find Eventual Safe States

1. Question

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 numberKso that for any choice of where to walk, we must have stopped at a terminal node in less thanKsteps.

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

The directed graph hasNnodes with labels0, 1, ..., N-1, whereNis the length ofgraph. The graph is given in the following form:graph[i]is a list of labelsjsuch 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.

Note:

• graphwill have length at most10000.

• The number of edges in the graph will not exceed32000.

• Eachgraph[i]

  will be a sorted list of different integers, chosen within the range[0, graph.length - 1].

2. Implementation

(1) BFS Topological Sort

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        // Method 1: BFS topologicl sort
        List<Integer> res = new ArrayList<>();

        if (graph == null || graph.length == 0) {
            return res;
        }

        int n = graph.length;
        int[] outDegree = new int[n];

        List<Set<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }

        for (int i = 0; i < n; i++) {
            for (int neighbor : graph[i]) {
                adjList.get(neighbor).add(i);
                ++outDegree[i];
            }
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (outDegree[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int curNode = queue.remove();
            res.add(curNode);

            for (int nextNode : adjList.get(curNode)) {
                if (--outDegree[nextNode] == 0) {
                    queue.add(nextNode);
                }
            }
        }

        Collections.sort(res);
        return res;
    }
}

3. Time & Space Complexity

BFS Topological Sort: