Algorithm Practice
Search…
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
Kso 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 has
Nnodes 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 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
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:
Last modified 2yr ago