Find Eventual Safe states

Problem Statement

Link : Find eventual safe states

A directed graph is given as graph, where graph[i] lists all nodes reachable directly from node i.

• A terminal node is one without outgoing edges.

• A safe node is one from which every possible path eventually leads to a terminal node or another safe node (i.e., never reaches a cycle).

Return all safe nodes in ascending order

Intuition

A node is safe if it cannot reach a cycle via any path. Terminal nodes are inherently safe.
We can reverse the graph and apply a Kahn-style topological peel: start from terminal nodes and propagate safety upstream. Nodes that feed cycles will never drop to indegree zero and thus remain unsafe

Alternatively, use DFS coloring: mark nodes during recursion to detect cycles; only paths avoiding cycles result in safe nodes

Approach 1: Reverse-Graph + Kahn’s Algorithm (BFS)

Steps

1. Build reversed adjacency list: for edge u → v in original graph, add v → u.

2. Compute indegree for each node based on original out-degrees.

3. Initialize a queue with all terminal nodes (indegree = 0).

4. While queue not empty:

   • Pop a safe node.

   • For each predecessor in reversed graph:

     • Decrement its indegree (i.e. one outgoing path now proven safe).

     • If indegree becomes 0, add it to queue.

5. Nodes collected are safe. Sort and return

Java‑style Code

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int N = graph.length;
        List<List<Integer>> rev = new ArrayList<>();
        for (int i = 0; i < N; i++) rev.add(new ArrayList<>());
        
        int[] indegree = new int[N];
        // Build reversed graph
        for (int i = 0; i < N; i++) {
            for (int j : graph[i]) {
                rev.get(j).add(i);
                indegree[i]++;
            }
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            if (indegree[i] == 0)
                q.add(i);
        }

        List<Integer> safe = new ArrayList<>();
        while (!q.isEmpty()) {
            int node = q.poll();
            safe.add(node);
            for (int prev : rev.get(node)) {
                if (--indegree[prev] == 0)
                    q.add(prev);
            }
        }

        Collections.sort(safe);
        return safe;
    }
}

Dry Run

graph = [[1,2],[2,3],[5],[0],[5],[],[]]

• Terminal nodes: 5, 6

• Reverse BFS: 5 → reduces predecessors → eventually collect [5, 4, 6, 2, 1?, 0?]

• Final sorted safe nodes: [0, 1, 2, 4, 5, 6] (depending on connectivity)

Complexity

• Time: O(V + E)

• Space: O(V + E) for reversed list, indegree, and queue

Approach 2: DFS with Coloring

Intuition

Use node coloring to track DFS state:

• 0 = unvisited

• 1 = visiting (in recursion stack)

• 2 = safe (all outgoing paths lead to safe nodes)

DFS a node:

• If you encounter another node with color 1 → cycle → return false.

• If all neighbors return true, mark current node safe and return true

Java‑style Code

class Solution {
    List<Integer> res = new ArrayList<>();
    int[] color; // 0=unvisited, 1=visiting, 2=safe

    public List<Integer> eventualSafeNodes(int[][] graph) {
        int N = graph.length;
        color = new int[N];
        for (int i = 0; i < N; i++) {
            if (dfs(graph, i))
                res.add(i);
        }
        Collections.sort(res);
        return res;
    }

    private boolean dfs(int[][] graph, int node) {
        if (color[node] != 0)
            return color[node] == 2;
        color[node] = 1; // start exploring
        for (int nei : graph[node]) {
            if (!dfs(graph, nei))
                return false;
        }
        color[node] = 2; // confirmed safe
        return true;
    }
}

Dry Run

graph = [[1,2],[2,3],[5],[0],[5],[],[]]

• dfs(0) explores path, eventually hits cycle chain → returns false

• Terminal nodes (e.g., node 5) get color = 2

• Their predecessors eventually become safe if all paths avoid cycles

• Final safe nodes: [2, 4, 5, 6]

Complexity

• Time: O(V + E)

• Space: O(V) for color array + recursion stack

Conclusion and Comparison

• Use Kahn’s Algorithm when you prefer iterative, queue-based processing.

• Use DFS coloring for recursion-style solutions with state tracking.

• Both approaches yield the same sorted list of safe nodes.