Find Eventual Safe States

1public List<Integer> eventualSafeNodes(int[][] graph) {
2    int n = graph.length;
3    // 0: unvisited, 1: visiting, 2: safe, 3: unsafe
4    int[] state = new int[n];
5
6    for (int i = 0; i < n; i++) {
7        if (state[i] == 0) {
8            dfs(i, graph, state);
9        }
10    }
11
12    List<Integer> result = new ArrayList<>();
13    for (int i = 0; i < n; i++) {
14        if (state[i] == 2) result.add(i);
15    }
16    return result;
17}
18
19private boolean dfs(int node, int[][] graph, int[] state) {
20    if (state[node] == 2) return true;   // Safe
21    if (state[node] == 3) return false;  // Unsafe
22    if (state[node] == 1) return false;  // Cycle
23
24    state[node] = 1;  // Mark as visiting
25
26    for (int neighbor : graph[node]) {
27        if (!dfs(neighbor, graph, state)) {
28            state[node] = 3;  // Unsafe
29            return false;
30        }
31    }
32
33    state[node] = 2;  // Mark as safe
34    return true;
35}