MediumDepth-First SearchBreadth-First SearchGraphTopological Sort

Find Eventual Safe States

1 approach, code in every language

You are given a directed graph with n nodes labeled 0 to n - 1, described by an adjacency list graph, where graph[i] lists all nodes reachable from node i in one step. A node with no outgoing edges is called terminal.

A node is safe if every walk that starts at it is guaranteed to reach a terminal node after a finite number of steps, no matter which edges are chosen. Equivalently, a node is safe only if none of its walks can get trapped in a cycle.

Return an array containing all safe nodes, sorted in ascending order.

Example 1

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

Output: [2,4,5,6]

Nodes 5 and 6 are terminal. Nodes 2 and 4 only lead into node 5, so every path ends. Nodes 0, 1, 3 can enter the cycle 0 -> 1 -> 3 -> 0 area and are unsafe.

Example 2

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

Output: [4]

Only node 4 is terminal, and every other node can reach a cycle, so 4 is the single safe node.

Constraints

n == graph.length
1 <= n <= 10^4
0 <= graph[i].length <= n
0 <= graph[i][j] <= n - 1
graph[i] is sorted in strictly increasing order.
The graph may contain self-loops.
The number of edges is in the range [1, 4 * 10^4].

DFS with Three-Color Marking

Run a depth-first search that paints nodes white, gray, or black to detect cycles and confirm safety.

Loading animation…

Intuition

A node is safe only if none of its outgoing paths ever loop, so cycle detection is the heart of the problem. We color each node with one of three states: unvisited, currently on the recursion stack (in-progress), and fully proven safe. When a DFS reaches an in-progress node it has closed a loop, which makes the current path unsafe. A node becomes safe only after every one of its neighbors has been confirmed safe. Because the safe color is committed only at the end of a successful exploration, we can trust the memoized result on later visits and never recompute it.

Algorithm walkthrough

1Give every node the color 0 (unvisited); use 1 for in-progress and 2 for confirmed safe.
2For each node, if it is already colored, return true only when its color is 2 (safe).
3Mark a freshly entered node as 1 (in-progress) and recurse into all of its neighbors.
4If any neighbor turns out unsafe, or if we reach a node already marked in-progress, this node is unsafe.
5If every neighbor is safe, commit the node's color to 2 and report it as safe.
6Run this from every node and collect, in index order, all nodes that finished with color 2.

Implementation

from typing import List

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        color = [0] * n  # 0 = unvisited, 1 = in-progress, 2 = safe

        def dfs(node: int) -> bool:
            if color[node] != 0:
                return color[node] == 2
            color[node] = 1
            for nxt in graph[node]:
                if not dfs(nxt):
                    return False
            color[node] = 2
            return True

        return [i for i in range(n) if dfs(i)]

Time

O(V + E)

Space

O(V + E)

Each node and edge is explored once; memoized colors prevent recomputation. Recursion depth is O(V).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

States From Which the Batch Always Halts is our own problem on the technique behind Find Eventual Safe States: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free