802. Find Eventual Safe States

802

MediumGraph DFS and BFSDFS coloring (white/gray/black)Cycle detection with three-state DFS

Find Eventual Safe States

Given a directed graph as an adjacency list, a node is 'terminal' if it has no outgoing edges and 'safe' if every possible path starting from it eventually reaches a terminal node (equivalently, no path from it can ever enter a cycle). Return all safe nodes in ascending order.

Open official problem prompt ↗

In plain English

Identify every node from which you cannot possibly wander into an infinite loop — all walks terminate at a dead-end node.

Picture it like this

Imagine one-way streets. A junction is 'safe' if no matter which turns you take you always end at a cul-de-sac. If any route from it can trap you circling a roundabout forever, it is unsafe.

Example

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Why: Nodes 5 and 6 are terminal; 2 only leads to 5 and 4 only leads to 5, so all their paths terminate. Nodes 0,1,3 sit on the cycle 0->1->3->0, so they are unsafe.

Constraints

n == graph.length1 <= n <= 10^40 <= graph[i].length <= n0 <= graph[i][j] <= n - 1graph[i] is sorted and has no duplicate valuesThe graph may contain self-loops and cycles

Pattern lesson

See the pattern, then code

Cycle detection with three-state DFS

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Color each node WHITE (unvisited), GRAY (on the current DFS stack), or BLACK (fully explored and confirmed safe). If DFS re-encounters a GRAY node it has closed a cycle, so the current node is unsafe. A node becomes BLACK/safe only after all its successors are proven safe.

New words, made simpleKnow these before the algorithm

Terminal node: A node with no outgoing edges — a guaranteed stopping point.
Safe node: A node from which every path ends at a terminal node.
Gray (visiting): A node currently on the recursion stack; revisiting it means a cycle.
Back edge: An edge to a gray node, the signature of a directed cycle.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Naive per-node reachability

Recomputes shared subproblems repeatedly; too slow for n up to 10^4.

For each node, explore all paths checking whether any hits a cycle.

Time O(V * (V + E))Space O(V)

Best choiceThree-state DFS with memo

Each node and edge is processed once and the answer is memoized in the color.

Color nodes white/gray/black; a gray revisit is a cycle, black means proven safe, and results are cached in the state array.

Time O(V + E)Space O(V)

Reverse-graph Kahn topological sort

Also correct and iterative; equivalent result, alternative to recursion.

Peel nodes by out-degree in the reversed graph; survivors on cycles never reach out-degree zero.

Time O(V + E)Space O(V)

The rule we keep true

Invariant

A node is marked state 2 only after every one of its successors has been confirmed safe; a node reachable from a gray node returns unsafe before any such mark can be made.

Why this is correct

Reasoning

DFS explores a node's entire successor set before coloring it black. If a successor is gray it lies on the current path, forming a cycle, so the node is correctly unsafe. Because the color memoizes the outcome, each node is fully evaluated once; safety propagates upward only through chains that provably terminate.

The algorithm in three movesSay these aloud before coding

1Give every node state 0 (unvisited); use 1 for 'visiting' and 2 for 'safe'

dfs(5): no edges -> state 2 (safe)

2Run DFS from each node; if already resolved, return whether its state is safe

dfs(2): ->5 safe -> state 2

3Mark the node visiting, then recurse into every successor

dfs(0): ->1 ->3 ->0 GRAY -> unsafe

4If any successor is not safe (including a visiting node still on the stack), the node is unsafe

answer = [2,4,5,6]

5Mark the node safe once all successors are safe; collect nodes whose DFS returns safe

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

0:cyc0

1:cyc1

2:safe2

3:cyc3

4:safe4

5:term5

6:term6

1 · Readnode 0 -> [1,2]

2 · AskSuccessors safe?

3 · Update statestate[0]=1 (gray)

4 · ResultRecurse into 1.

Key takeaway

Terminal 5,6 and their feeders 2,4 are safe; the 0-1-3 cycle poisons those nodes.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-8Memo short-circuit
A non-zero state means the node is resolved: return True only when it is state 2 (safe). A gray node (state 1) returns False, flagging the cycle.
2
Lines 9-13Mark gray and recurse
Setting state 1 before recursing lets a downstream back edge detect this node on the stack; any unsafe successor makes this node unsafe.
3
Lines 14-16Promote to safe
Only after all successors succeed is the node colored 2, permanently caching its safety.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A self-loop node i in graph[i] -> node is unsafe (immediate cycle)
All nodes terminal (no edges) -> every node is safe
Fully cyclic graph -> empty result
Disconnected components -> the outer loop calls dfs on every node

Common beginner mistakes

Using a simple visited boolean, which cannot distinguish 'on stack' (cycle) from 'finished safe'
Marking a node safe before its successors are verified
Forgetting that graph[node] can be empty (that is the terminal base case, and the for-loop handles it by falling through to safe)
Deep recursion on n=10^4 chains risking stack limits — acceptable here but worth noting an iterative alternative

Check your understanding

Why is a plain two-state visited flag insufficient, unlike in undirected cycle detection?

PyPython 3 · solution.py

Optimal

1class Solution:2    def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:3        n = len(graph)4        state = [0] * n  # 0 = unvisited, 1 = visiting, 2 = safe56        def dfs(node: int) -> bool:7            if state[node] != 0:8                return state[node] == 29            state[node] = 110            for nei in graph[node]:11                if not dfs(nei):12                    return False13            state[node] = 214            return True1516        return [i for i in range(n) if dfs(i)]

Time complexityO(V + E)Optimized

Space complexityO(V) for the state array and recursion stackExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonBloomberg

Find Eventual Safe States

Find Eventual Safe States

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS