Given a directed graph, find all safe nodes. A node is safe if every possible path starting from that node leads to a terminal node (no outgoing edges) or another safe node.
Input: [[1,2],[2,3],[5],[0],[5],[],[]] → Output: [2,4,5,6]Input: [[1,2,3,4],[1,2],[3,4],[0,4],[]] → Output: [4]
A node is unsafe if it is part of a cycle. Use DFS with three states: 0=unvisited, 1=visiting (in current path), 2=safe.
- DFS from each node. State: 0=unvisited, 1=visiting, 2=safe.
- If state==1 (cycle detected): return false (unsafe).
- If state==2: return true (safe).
- Mark as visiting (1). If any neighbor is unsafe, mark as unsafe (1 stays), return false.
- Mark as safe (2), return true.
import java.util.*;
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
int n = graph.length;
int[] state = new int[n]; // 0=unvisited, 1=visiting, 2=safe
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) if (isSafe(graph, state, i)) res.add(i);
return res;
}
private boolean isSafe(int[][] graph, int[] state, int node) {
if (state[node] > 0) return state[node] == 2;
state[node] = 1; // visiting
for (int next : graph[node]) {
if (!isSafe(graph, state, next)) return false;
}
state[node] = 2; // safe
return true;
}
}
- Time Complexity: O(V+E)
- Space Complexity: O(V)