Find Eventual Safe States

How it works

Think of safe nodes as those that can reach terminal nodes. If we reverse the edge directions, safe nodes are those reachable from terminal nodes. Using Kahn's algorithm on this reversed perspective: terminal nodes have zero out-degree in the original graph. We start from these terminal nodes and work backward, removing edges. Any node whose out-degree reaches zero is safe because all its paths lead to already-confirmed safe nodes.

Steps

1. Build a reverse adjacency list (parents) and track the out-degree of each node.
2. Add all terminal nodes (out-degree = 0) to a queue.
3. Process nodes from the queue:
   • For each parent of the current node, decrement its out-degree.
   • If a parent's out-degree becomes 0, add it to the queue.
4. After processing, all nodes with out-degree 0 are safe.
5. Return the safe nodes in sorted order.

Complexity

• Time complexity: O(V + E)
• Space complexity: O(V + E)

Where V is the number of vertices and E is the number of edges in the given graph.

Things to watch for

Confusing Visited with Safe Status

A node being visited during DFS does not mean it is safe. You need separate tracking for "currently being explored" (to detect cycles) and "confirmed safe" (all paths lead to terminal nodes). Mixing these states causes incorrect cycle detection or premature safety classification.

Not Returning Results in Sorted Order

The problem requires returning safe nodes in ascending order. If you collect nodes as they are confirmed safe during DFS, the order depends on traversal order, not node indices. Either sort the result at the end or iterate through nodes 0 to n-1 and check each one's safety status.

Incorrectly Handling Nodes with No Outgoing Edges

Terminal nodes (nodes with no outgoing edges) are always safe by definition. In the topological sort approach, these nodes have out-degree 0 and should be the starting points. In DFS, they should immediately return true without further recursion.

from typing import List
from collections import deque

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        outdegree = [0] * n
        parents = [[] for _ in range(n)]
        queue = deque()

        for node in range(n):
            outdegree[node] = len(graph[node])
            if outdegree[node] == 0:
                queue.append(node)
            for nei in graph[node]:
                parents[nei].append(node)

        while queue:
            node = queue.popleft()
            for parent in parents[node]:
                outdegree[parent] -= 1
                if outdegree[parent] == 0:
                    queue.append(parent)

        res = []
        for node in range(n):
            if outdegree[node] <= 0:
                res.append(node)
        return res

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> outdegree(n, 0);
        vector<vector<int>> parents(n);
        queue<int> q;

        for (int node = 0; node < n; node++) {
            outdegree[node] = graph[node].size();
            if (outdegree[node] == 0) {
                q.push(node);
            }
            for (int nei : graph[node]) {
                parents[nei].push_back(node);
            }
        }

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int parent : parents[node]) {
                outdegree[parent]--;
                if (outdegree[parent] == 0) {
                    q.push(parent);
                }
            }
        }

        vector<int> res;
        for (int node = 0; node < n; node++) {
            if (outdegree[node] <= 0) {
                res.push_back(node);
            }
        }
        return res;
    }
};