Find Eventual Safe States

Share

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.

Example 1
Input: [[1,2],[2,3],[5],[0],[5],[],[]] → Output: [2,4,5,6]
Example 2
Input: [[1,2,3,4],[1,2],[3,4],[0,4],[]] → Output: [4]

Solution Approach

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.
Java
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)