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 number`K`so that for any choice of where to walk, we must have stopped at a terminal node in less than`K`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.
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:
• `graph`will have length at most`10000`.
• The number of edges in the graph will not exceed`32000`.
• Each`graph[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
14
â€‹
15
for (int i = 0; i < n; i++) {
16
17
}
18
â€‹
19
for (int i = 0; i < n; i++) {
20
for (int neighbor : graph[i]) {
21
22
++outDegree[i];
23
}
24
}
25
â€‹
26
27
â€‹
28
for (int i = 0; i < n; i++) {
29
if (outDegree[i] == 0) {
30
31
}
32
}
33
â€‹
34
while (!queue.isEmpty()) {
35
int curNode = queue.remove();
36
37
â€‹
38
for (int nextNode : adjList.get(curNode)) {
39
if (--outDegree[nextNode] == 0) {
40
41
}
42
}
43
}
44
â€‹
45
Collections.sort(res);
46
return res;
47
}
48
}
Copied!

# 3. Time & Space Complexity

BFS Topological Sort: