Code Implementation

class Solution:
    def eventualSafeNodes(self, graph):
        n = len(graph)
        color = [0] * n  # 0=unvisited, 1=visiting, 2=safe

        def dfs(node):
            if color[node] != 0:
                return color[node] == 2
            color[node] = 1
            for nei in graph[node]:
                if color[nei] == 2:
                    continue
                if color[nei] == 1 or not dfs(nei):
                    return False
            color[node] = 2
            return True

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

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0); // 0=unvisited, 1=visiting, 2=safe
        vector<int> res;

        function<bool(int)> dfs = [&](int node) {
            if (color[node] != 0) return color[node] == 2;
            color[node] = 1;
            for (int nei : graph[node]) {
                if (color[nei] == 2) continue;
                if (color[nei] == 1 || !dfs(nei)) return false;
            }
            color[node] = 2;
            return true;
        };

        for (int i = 0; i < n; ++i)
            if (dfs(i)) res.push_back(i);
        return res;
    }
};
      

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n]; // 0=unvisited, 1=visiting, 2=safe
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < n; ++i) {
            if (dfs(graph, color, i)) res.add(i);
        }
        return res;
    }

    private boolean dfs(int[][] graph, int[] color, int node) {
        if (color[node] != 0) return color[node] == 2;
        color[node] = 1;
        for (int nei : graph[node]) {
            if (color[nei] == 2) continue;
            if (color[nei] == 1 || !dfs(graph, color, nei)) return false;
        }
        color[node] = 2;
        return true;
    }
}
      

var eventualSafeNodes = function(graph) {
    const n = graph.length;
    const color = new Array(n).fill(0); // 0=unvisited, 1=visiting, 2=safe

    function dfs(node) {
        if (color[node] !== 0) return color[node] === 2;
        color[node] = 1;
        for (const nei of graph[node]) {
            if (color[nei] === 2) continue;
            if (color[nei] === 1 || !dfs(nei)) return false;
        }
        color[node] = 2;
        return true;
    }

    const res = [];
    for (let i = 0; i < n; ++i) {
        if (dfs(i)) res.push(i);
    }
    return res;
};
      

Problem Description

You are given a directed graph represented as an adjacency list, where graph[i] is a list of nodes that node i points to. A node is called eventually safe if, starting from that node, every possible path leads to a terminal node (a node with no outgoing edges) or another safe node, and never leads to a cycle.

Your task is to return a list of all the eventual safe nodes in ascending order.

• Each node can appear in the result at most once.
• The input graph is a list of lists of integers.
• The returned list must be sorted in increasing order.

Thought Process

First, let's understand what makes a node "safe": it must not be possible to start from that node and get stuck in a cycle, no matter which path you take. If a node leads only to terminal nodes (or to other safe nodes), it's safe. If it can reach a cycle, it's not safe.

A brute-force approach would be to try all paths starting from each node and see if any path leads to a cycle. But this is inefficient because there can be exponential numbers of paths.

To optimize, we need a way to avoid redundant work and quickly detect cycles. We can use depth-first search (DFS) with memoization (caching results) and a way to mark nodes as "visiting" to detect cycles during DFS. If we revisit a "visiting" node, we've found a cycle. If we finish exploring a node and find all its paths are safe, we mark it as safe.

Solution Approach

We use a DFS-based coloring algorithm to classify nodes:

• Color 0: Node has not been visited yet.
• Color 1: Node is being visited (in the current DFS path).
• Color 2: Node is known to be safe (all paths from it terminate safely).

1. For each node, if it is unvisited (color[node] == 0), start a DFS from that node.
2. During DFS, mark the node as visiting (color[node] = 1).
3. For each neighbor, check:
   • If the neighbor is already safe (color[nei] == 2), continue.
   • If the neighbor is visiting, a cycle is detected; return false.
   • If the neighbor is unvisited, recursively DFS on it. If any neighbor is unsafe, return false.
4. If all neighbors are safe, mark the node as safe (color[node] = 2) and return true.
5. Collect all nodes that are marked safe and return them sorted.

This approach ensures that each node is processed at most once, and cycles are detected efficiently.

Example Walkthrough

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

• Node 0 points to 1 and 2
• Node 1 points to 2 and 3
• Node 2 points to 5
• Node 3 points to 0
• Node 4 points to 5
• Node 5 has no outgoing edges (terminal)
• Node 6 has no outgoing edges (terminal)

1. Start with node 0: explore 1, which explores 2, which explores 5 (terminal, safe). Backtrack: 2 is safe.
2. Node 1 also points to 3. 3 points to 0. 0 is already being visited (cycle detected), so 1 is unsafe.
3. Node 0, because it can reach a cycle via 1→3→0, is also unsafe.
4. Node 4 points to 5 (safe), so 4 is safe.
5. Nodes 5 and 6 are terminal, so they are safe.
6. Node 2 points only to 5 (safe), so 2 is safe.
7. Node 3 points to 0, which is unsafe, so 3 is unsafe.

Time and Space Complexity

• Brute-force approach: For each node, exploring all possible paths can take exponential time, up to O(2^N) in the worst case.
• Optimized DFS with coloring:
  • Time Complexity: O(N + E), where N is the number of nodes and E is the number of edges. Each node and edge is visited at most once.
  • Space Complexity: O(N) for the color/state array and call stack (in the worst case of a linear graph).

Summary

The "Find Eventual Safe States" problem asks us to identify all nodes in a directed graph that cannot reach a cycle, no matter which path is chosen. By using DFS with a coloring scheme, we efficiently detect cycles and avoid redundant computation. This approach is both intuitive and optimal for sparse and dense graphs, making it a robust solution for this class of problems. The key insight is to cache results and use cycle detection during DFS, which brings the complexity down to linear in the size of the graph.