Problem statement

You are given a directed graph as an adjacency list, where graph[i] lists the nodes reachable in one step from i. A node is terminal if it has no outgoing edges, and safe if every path starting there reaches a terminal node.

Return all safe nodes in ascending order.

Example 1

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

Example 2

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

Example 3

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

Constraints

• 1 <= graph.length <= 30
• 0 <= graph[i][j] < graph.length
• The graph may contain cycles.

Hints for Find Eventual Safe States

1. Hint 1

   A node is unsafe exactly when it can reach a cycle.

2. Hint 2

   Run a DFS with three colours: unvisited, on-stack, and finished — meeting an on-stack node means a cycle.

3. Hint 3

   Cache the verdict per node so each is explored once; alternatively, run a topological sort on the reversed graph.

How to solve Find Eventual Safe States

A node is unsafe iff it can reach a cycle. Run a three-colour DFS (unvisited / on-stack / finished) and cache each node's verdict.

Approach

1. Mark node on-stack; recurse into each successor.
2. If any successor is unsafe (or on-stack), mark node unsafe and return false.
3. Otherwise mark node safe; collect nodes whose verdict is safe.

Why it works

Meeting an on-stack node means a back edge, hence a cycle, and any node that can reach a cycle inherits the unsafe verdict; memoising verdicts makes each node explored once.

Complexity

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

Pitfalls

• Kahn's algorithm on the reversed graph (peeling terminal nodes) is the iterative alternative.

Reference solution

Python

import sys

def eventualSafeNodes(graph):
    sys.setrecursionlimit(10000)
    n = len(graph)
    state = [0] * n

    def safe(node):
        if state[node] == 2:
            return True
        if state[node] in (1, 3):
            return False
        state[node] = 1
        for nxt in graph[node]:
            if not safe(nxt):
                state[node] = 3
                return False
        state[node] = 2
        return True

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

Java

private static boolean isSafe(int[][] graph, int[] state, int node) {
    if (state[node] == 2) return true;
    if (state[node] == 1 || state[node] == 3) return false;
    state[node] = 1;
    for (int next : graph[node]) {
        if (!isSafe(graph, state, next)) {
            state[node] = 3;
            return false;
        }
    }
    state[node] = 2;
    return true;
}

public static int[] eventualSafeNodes(int[][] graph) {
    int n = graph.length;
    int[] state = new int[n];
    List<Integer> out = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (isSafe(graph, state, i)) out.add(i);
    }
    int[] result = new int[out.size()];
    for (int i = 0; i < out.size(); i++) result[i] = out.get(i);
    return result;
}

C++

static bool isSafe(vector<vector<int>>& graph, vector<int>& state, int node) {
    if (state[node] == 2) return true;
    if (state[node] == 1 || state[node] == 3) return false;
    state[node] = 1;
    for (int next : graph[node]) {
        if (!isSafe(graph, state, next)) {
            state[node] = 3;
            return false;
        }
    }
    state[node] = 2;
    return true;
}

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
    int n = (int) graph.size();
    vector<int> state(n, 0);
    vector<int> out;
    for (int i = 0; i < n; i++) {
        if (isSafe(graph, state, i)) out.push_back(i);
    }
    return out;
}

JavaScript

var eventualSafeNodes = function(graph) {
    const n = graph.length;
    const state = [];
    for (let i = 0; i < n; i++) state.push(0);
    const safe = function(node) {
        if (state[node] === 2) return true;
        if (state[node] === 1 || state[node] === 3) return false;
        state[node] = 1;
        for (let i = 0; i < graph[node].length; i++) {
            if (!safe(graph[node][i])) {
                state[node] = 3;
                return false;
            }
        }
        state[node] = 2;
        return true;
    };
    const out = [];
    for (let i = 0; i < n; i++) {
        if (safe(i)) out.push(i);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Implement Magic Dictionary Medium
• Design Add and Search Words Data Structure Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium