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.
1
Example:
2
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
3
4
Output:
5
[2,4,5,6]
6
Here is a diagram of the above graph.
Copied!
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
1
class Solution {
2
public List<Integer> eventualSafeNodes(int[][] graph) {
3
// Method 1: BFS topologicl sort
4
List<Integer> res = new ArrayList<>();
5
6
if (graph == null || graph.length == 0) {
7
return res;
8
}
9
10
int n = graph.length;
11
int[] outDegree = new int[n];
12
13
List<Set<Integer>> adjList = new ArrayList<>();
14
15
for (int i = 0; i < n; i++) {
16
adjList.add(new HashSet<>());
17
}
18
19
for (int i = 0; i < n; i++) {
20
for (int neighbor : graph[i]) {
21
adjList.get(neighbor).add(i);
22
++outDegree[i];
23
}
24
}
25
26
Queue<Integer> queue = new LinkedList<>();
27
28
for (int i = 0; i < n; i++) {
29
if (outDegree[i] == 0) {
30
queue.add(i);
31
}
32
}
33
34
while (!queue.isEmpty()) {
35
int curNode = queue.remove();
36
res.add(curNode);
37
38
for (int nextNode : adjList.get(curNode)) {
39
if (--outDegree[nextNode] == 0) {
40
queue.add(nextNode);
41
}
42
}
43
}
44
45
Collections.sort(res);
46
return res;
47
}
48
}
Copied!

3. Time & Space Complexity

BFS Topological Sort: