Back to DSA
Find Eventual Safe States
easyIn a directed graph of n nodes (0 to n-1), a node is terminal if it has no outgoing edges. A node is safe if every path originating from it eventually reaches a terminal node (i.e., the node is not part of any cycle). Return all safe nodes in ascending order.
Examples
Example 1:
Input:
graph = [[1,2],[2,3],[5],[0],[5],[],[]]Output:
[2,4,5,6]Explanation: Nodes 5 and 6 are terminal. Node 4 leads only to 5. Node 2 leads only to 5. Nodes 0, 1, and 3 participate in a cycle and are unsafe.
Example 2:
Input:
graph = [[],[0],[1],[2]]Output:
[0,1,2,3]Explanation: No cycles exist. Node 0 is terminal; all others eventually lead to node 0.
Hints
import java.util.*;
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
int n = graph.length;
int[] color = new int[n]; // 0=white, 1=gray, 2=black
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (dfs(graph, i, color)) result.add(i);
}
return result;
}
private boolean dfs(int[][] graph, int node, int[] color) {
if (color[node] != 0) return color[node] == 2;
color[node] = 1;
for (int next : graph[node]) {
if (!dfs(graph, next, color)) return false;
}
color[node] = 2;
return true;
}
}Time complexity
O(V + E)Space complexity
O(V)