Time Complexity: $O(V \cdot (V + E))$. In the worst case, for every node, we might traverse a large portion of the graph. Why it fails: This approach results in a Time Limit Exceeded (TLE) error. The constraints allow up to $10^4$ nodes. Re-traversing the same paths repeatedly for different starting nodes performs highly redundant work. We need a way to remember (memoize) whether a node is safe or unsafe once we process it.

Core Insight for Find Eventual Safe States

The key intuition is that we can classify every node into one of three states during a DFS traversal. This is often called the 3-Color DFS technique.

1. Unvisited (White/0): The node has not been processed yet.
2. Visiting (Gray/1): The node is currently in the recursion stack (we are exploring its descendants). If we encounter a node in this state, we have found a cycle.
3. Safe (Black/2): The node and all its descendants have been fully processed, and no cycle was found.

The invariant we maintain is this: A node is safe if and only if all its neighbors are safe.

If we start DFS from a node and encounter a node marked "Visiting" (Gray), we know a cycle exists. Consequently, the current node and all nodes in the current recursion stack are unsafe. If we finish processing a node and all its neighbors return "Safe" (or it has no neighbors), then the node itself is "Safe" (Black).

By persisting these states globally, we avoid re-calculating the safety of a node. If we encounter a "Safe" node, we return true immediately. If we encounter a "Visiting" node (which effectively becomes a marker for "Unsafe" in our final logic), we return false.

Visual Description: Imagine the DFS as a path growing from a source. As we step onto a node, we mark it "Visiting". We then step to its neighbor. If that path eventually loops back to a "Visiting" node, the entire active path is "poisoned" by the cycle. If the path reaches a dead end (terminal node), we backtrack, marking nodes as "Safe" only after verifying all their outgoing paths are safe.

Execution Flow

Let's trace the algorithm with a simple example: 0 -> 1 -> 0 (Cycle) and 2 -> 1.

1. Start Loop: i = 0. color[0] is 0. Call dfs(0).
2. DFS(0): Mark color[0] = 1. Neighbor is 1.
3. DFS(1): Mark color[1] = 1. Neighbor is 0.
4. Check Neighbor 0: color[0] is 1. Cycle detected! Return false.
5. Back to DFS(1): Received false from neighbor 0. Return false. color[1] remains 1.
6. Back to DFS(0): Received false from neighbor 1. Return false. color[0] remains 1.
7. Loop continues: i = 1. color[1] is 1. It was visited and determined unsafe. Skip or treat as processed.
8. Loop continues: i = 2. color[2] is 0. Call dfs(2).
9. DFS(2): Mark color[2] = 1. Neighbor is 1.
10. Check Neighbor 1: color[1] is 1. This means it is unsafe (either in stack or previously failed). Return false.
11. Back to DFS(2): Received false from neighbor 1. Return false. color[2] remains 1.
12. Final Result: No nodes marked 2. Result [].

Note: In this logic, state 1 serves double duty as "Visiting" and "Unsafe". State 2 is strictly "Safe".

Proof of Correctness

The correctness relies on the invariant of the 3-color DFS.

1. Cycle Detection: A directed graph has a cycle if and only if a DFS encounters a back-edge to a node currently in the recursion stack (state 1). Our algorithm explicitly checks for this.
2. Propagation: If a node u has a neighbor v that is part of a cycle (or leads to one), dfs(v) will return false. Consequently, dfs(u) will also return false, correctly identifying u as unsafe.
3. Terminal Nodes: A terminal node has no neighbors. The loop over neighbors completes immediately, the node is marked 2 (Safe), and true is returned. This forms the base case for safety.
4. Completeness: By iterating 0 to n-1, we ensure every component of the graph is processed. Memoization ensures each node is computed exactly once.

Reference Implementation

C++ Solution for LeetCode 802

cpp
class Solution {
public:
    // 0: Unvisited
    // 1: Visiting (in stack) or Unsafe
    // 2: Safe
    bool dfs(int node, vector<vector<int>>& graph, vector<int>& color) {
        if (color[node] != 0) {
            return color[node] == 2;
        }

        color[node] = 1; // Mark as visiting

        for (int neighbor : graph[node]) {
            if (color[neighbor] == 2) continue; // Safe node, skip
            if (color[neighbor] == 1 || !dfs(neighbor, graph, color)) {
                return false; // Cycle detected or leads to unsafe node
            }
        }

        color[node] = 2; // Mark as safe
        return true;
    }

    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0);
        vector<int> safeNodes;

        for (int i = 0; i < n; ++i) {
            if (dfs(i, graph, color)) {
                safeNodes.push_back(i);
            }
        }

        return safeNodes;
    }
};

Java Solution for LeetCode 802

java
class Solution {
    // 0: Unvisited, 1: Visiting/Unsafe, 2: Safe
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        List<Integer> result = new ArrayList<>();

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

    private boolean dfs(int node, int[][] graph, int[] color) {
        if (color[node] != 0) {
            return color[node] == 2;
        }

        color[node] = 1; // Mark as visiting

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

        color[node] = 2; // Mark as safe
        return true;
    }
}

Python Solution for LeetCode 802

python
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        # 0: Unvisited
        # 1: Visiting (in recursion stack) or Unsafe
        # 2: Safe
        color = [0] * n

        def dfs(node):
            if color[node] != 0:
                return color[node] == 2
            
            color[node] = 1 # Mark as visiting
            
            for neighbor in graph[node]:
                if color[neighbor] == 2:
                    continue
                if color[neighbor] == 1 or not dfs(neighbor):
                    return False
            
            color[node] = 2 # Mark as safe
            return True

        res = []
        for i in range(n):
            if dfs(i):
                res.append(i)
        
        return res