Find Eventual Safe States

Problem in Plain English

Return the directed graph nodes from which every possible walk eventually reaches a terminal node. Any node that can reach a directed cycle is unsafe.

Problem Statement

The adjacency list graph describes nodes 0 through n - 1: each value in graph[u] is the destination of an edge from u. A terminal node has no outgoing edges. A node is safe if every possible path starting there eventually terminates.

Return all safe nodes in ascending order. Self-loops are allowed. One terminating choice is insufficient: if another choice can enter a cycle, the node is unsafe.

Constraints

n == graph.length; 1 <= n <= 10^4
0 <= graph[u].length <= n; destinations are in [0, n - 1].
Each adjacency list is strictly increasing; self-loops are allowed.
1 <= total number of edges <= 4 * 10^4

Examples

Example 1

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]

Nodes 0, 1 and 3 form a cycle. Nodes 2 and 4 go only to terminal 5, and 6 is terminal. An exit from the cycle to 2 does not make cycle nodes safe.

Example 2

Input: graph = [[0]]
Output: []

The smallest graph has one self-loop. A walk can stay at 0 forever, so its singleton SCC is cyclic and unsafe.

Example 3

Input: graph = [[1,2],[1],[]]
Output: [2]

Node 1 loops to itself. Node 0 can choose terminal 2 but can also choose 1, so unsafety propagates to 0. Only 2 is safe.

Intuition

A strongly connected component (SCC) groups nodes that can all reach each other. A component with several nodes contains a cycle; a singleton is cyclic only if it has a self-loop. In Example 1, {0,1,3} is cyclic, while 2, 4, 5 and 6 cannot reach it. Tarjan finds these groups in one DFS. Reverse the edges between groups and spread an unsafe mark backward from every cyclic group to all groups that can reach it.

Approaches

Tarjan SCC

Optimal

Solution Details

Reveal Tarjan SCC: intuition, complexity, and code

Intuition

Collapse cycles with Tarjan SCC, then propagate unsafety backward. This linear-time approach explicitly exposes the cyclic groups and their predecessors; an explicit DFS frame stack supports deep graphs without recursion. Reverse topological elimination is a simpler alternative when the components themselves are not needed.

Step-by-Step Logic

Assign each discovered node a discovery index and low link. Maintain both DFS frames and an active SCC stack; they serve different purposes.
In Example 1 DFS discovers 0,1,2,5. Finish 5 and then 2 as singleton components; an edge to already-finished 2 must not lower another component’s low link.
Continue from 1 to 3. Edge 3 to active 0 lowers low[3] to 0; returning lowers low[1] to 0. Finishing 0 pops {3,1,0} together.
The remaining DFS roots 4 and 6 finish singleton components. Sizes greater than one mark {0,1,3} cyclic; also inspect every singleton for a self-loop.
Build reversed edges between distinct components. Starting with the cyclic component, mark every predecessor unsafe using a queue.
Scan node indices 0 through 6 and emit only nodes in unmarked components: [2,4,5,6].

Why It Works

Tarjan’s active stack holds discovered vertices not yet assigned to a finished SCC. low[u] records the earliest discovery reachable through the explored DFS descendants and an edge to that active stack. A finished child propagates its low link to its DFS parent; an edge to an active vertex uses that vertex’s discovery index; an edge to a completed SCC is ignored. When low[u] equals its discovery index, no vertex above u on the active stack can reach an earlier active vertex, so the stack suffix through u is exactly one SCC. After all components are assigned, their cross-component graph is acyclic. A component is cyclic exactly when its size exceeds one or it has a self-loop. Reverse-edge propagation marks exactly the components that can reach a cyclic one. In a finite graph, an infinite walk must repeat a vertex and thus reach a cycle; conversely a reachable cycle permits a nonterminating walk. Unmarked nodes are therefore exactly safe, and scanning indices yields ascending order.

Dry Run

Tarjan SCC: variable states at each step
Event	Discovery / low state	Component or classification
Discover 0,1,2,5	indices 0,1,2,3; lows initially same	active [0,1,2,5]
Finish 5 then 2	low[5]=3, low[2]=2	components {5}, {2}; active [0,1]
Discover 3; edge 3 to 0	index[3]=4; low[3]=0	active [0,1,3]
Return 3 to 1	low[1]=0	no component popped at 1
Finish 0	low[0]=0	pop {3,1,0}; cyclic
Discover 4 then 6	indices 5 then 6	components {4}, {6}
Reverse propagation	only {0,1,3} marked unsafe	no outside component reaches it
Scan node indices	unmarked 2,4,5,6	return [2,4,5,6]

Complexity Analysis

Time Complexity

O(n + m)

Space Complexity

O(n + m)

For n vertices and m edges, each DFS adjacency entry is processed once, each vertex is pushed and popped once per stack, and the component-edge scan and reverse BFS cost O(n + m). Arrays and stacks use O(n), while reversed component edges use O(m). Duplicate component edges are harmless and retained, avoiding sorting or deduplication costs. Output is collected in ascending order without a sort.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public List<Integer> eventualSafeNodes(int[][] graph) {5        int n = graph.length, clock = 0;6        int[] disc = new int[n], low = new int[n], next = new int[n];7        int[] parent = new int[n], comp = new int[n];8        Arrays.fill(disc, -1); Arrays.fill(parent, -1);9        boolean[] active = new boolean[n];10        Deque<Integer> frames = new ArrayDeque<>(), members = new ArrayDeque<>();11        List<Integer> sizes = new ArrayList<>();12        for (int root = 0; root < n; root++) {13            if (disc[root] != -1) continue;14            disc[root] = low[root] = clock++;15            frames.push(root); members.push(root); active[root] = true;16            while (!frames.isEmpty()) {17                int u = frames.peek();18                if (next[u] < graph[u].length) {19                    int v = graph[u][next[u]++];20                    if (disc[v] == -1) {21                        parent[v] = u; disc[v] = low[v] = clock++;22                        frames.push(v); members.push(v); active[v] = true;23                    } else if (active[v]) low[u] = Math.min(low[u], disc[v]);24                } else {25                    frames.pop();26                    if (low[u] == disc[u]) {27                        int size = 0, v;28                        do {29                            v = members.pop(); active[v] = false;30                            comp[v] = sizes.size(); size++;31                        } while (v != u);32                        sizes.add(size);33                    }34                    if (parent[u] != -1) low[parent[u]] = Math.min(low[parent[u]], low[u]);35                }36            }37        }38        int count = sizes.size();39        List<List<Integer>> reverse = new ArrayList<>();40        boolean[] bad = new boolean[count];41        for (int c = 0; c < count; c++) {42            reverse.add(new ArrayList<>()); bad[c] = sizes.get(c) > 1;43        }44        for (int u = 0; u < n; u++) for (int v : graph[u]) {45            if (u == v) bad[comp[u]] = true;46            if (comp[u] != comp[v]) reverse.get(comp[v]).add(comp[u]);47        }48        Deque<Integer> queue = new ArrayDeque<>();49        for (int c = 0; c < count; c++) if (bad[c]) queue.addLast(c);50        while (!queue.isEmpty()) {51            int c = queue.removeFirst();52            for (int pred : reverse.get(c)) if (!bad[pred]) {53                bad[pred] = true; queue.addLast(pred);54            }55        }56        List<Integer> answer = new ArrayList<>();57        for (int u = 0; u < n; u++) if (!bad[comp[u]]) answer.add(u);58        return answer;59    }60}

Hints

Hint 1

A node is unsafe precisely when some reachable walk can loop forever.

Hint 2

Group mutually reachable nodes into SCCs. A singleton still needs a self-loop check.

Hint 3

Find SCCs with Tarjan’s active stack and low links, then traverse reversed component edges from cyclic components.

Edge Cases

A self-loop makes even a one-node component unsafe.
A cycle with an exit to a terminal remains unsafe; every path must terminate.
A long chain ending at a terminal is safe; a long chain ending in a cycle is entirely unsafe.
Edges into completed SCCs must not merge them with the current active component.

Common Mistakes and Interview Tips

Confusing the DFS frame stack with the SCC stack; a node can leave its frame while remaining an active SCC member.
Using low[v] for an arbitrary active edge rather than disc[v], or updating from a vertex already assigned to a completed SCC.
Marking only vertices inside cycles and forgetting predecessors that can reach those cycles.
Treating a single terminating branch as enough to establish safety.

Key Takeaway

Collapse mutual reachability into components, classify the cyclic ones locally, and propagate their consequences through the acyclic component graph.