Find Eventual Safe States

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

1. 1Give every node the color 0 (unvisited); use 1 for in-progress and 2 for confirmed safe.
2. 2For each node, if it is already colored, return true only when its color is 2 (safe).
3. 3Mark a freshly entered node as 1 (in-progress) and recurse into all of its neighbors.
4. 4If any neighbor turns out unsafe, or if we reach a node already marked in-progress, this node is unsafe.
5. 5If every neighbor is safe, commit the node's color to 2 and report it as safe.
6. 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)]