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 numberK
so that for any choice of where to walk, we must have stopped at a terminal node in less thanK
steps.
Which nodes are eventually safe? Return them as an array in sorted order.
The directed graph hasN
nodes with labels0, 1, ..., N-1
, whereN
is the length ofgraph
. The graph is given in the following form:graph[i]
is a list of labelsj
such 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:
graph
will 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
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;
}
}
(2) DFS
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
List<Integer> res = new ArrayList();
if (graph == null || graph.length == 0) {
return res;
}
int n = graph.length;
int[] color = new int[n];
for (int i = 0; i < n; i++) {
if (!hasCycle(i, color, graph)) {
res.add(i);
}
}
return res;
}
public boolean hasCycle(int node, int[] color, int[][] graph) {
if (color[node] == 1) {
return true;
}
if (color[node] == 2) {
return false;
}
color[node] = 1;
for (int nextNode : graph[node]) {
if (hasCycle(nextNode, color, graph)) {
return true;
}
}
color[node] = 2;
return false;
}
}
3. Time & Space Complexity
BFS Topological Sort:
DFS: Time: O(n), Space: O(n)
Last updated
Was this helpful?