802. Find Eventual Safe States

Problem¶

Given a directed graph, return all nodes from which every path eventually reaches a node with no outgoing edges. Return them in ascending order.

graph = [[1,2],[2,3],[5],[0],[5],[],[]]
safe paths only: 2 -> 5, 4 -> 5, 5, 6
output = [2,4,5,6]

Key trick¶

Reverse the edges and run a topological process from terminal nodes. Whenever all outgoing edges of a node have been eliminated, that node is safe too.

Trap¶

An unsafe node does not have to belong to a cycle; reaching any cycle makes it unsafe.
Because every path must terminate, one outgoing edge leading to an unsafe node makes the source unsafe.
DFS implementations need distinct states for unvisited, currently visiting, safe, and unsafe; a single seen set is insufficient for memoization.

Why is it interesting?¶

It converts an all-paths cycle problem into reverse topological sorting: safe nodes are exactly those eliminated by repeatedly removing terminal nodes.

Python solution¶

from collections import deque


class Solution:
    def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:
        n = len(graph)
        predecessors = [[] for _ in range(n)]
        outdegree = [len(neighbors) for neighbors in graph]

        # Reverse every edge so safety can propagate from terminal nodes.
        for node, neighbors in enumerate(graph):
            for nei in neighbors:
                predecessors[nei].append(node)

        q = deque(node for node in range(n) if outdegree[node] == 0)
        safe = [False] * n

        while q:
            node = q.popleft()
            safe[node] = True

            # Removing a safe outgoing edge may make its predecessor safe.
            for prev in predecessors[node]:
                outdegree[prev] -= 1
                if outdegree[prev] == 0:
                    q.append(prev)

        # Scanning node labels guarantees ascending order.
        return [node for node in range(n) if safe[node]]

Time complexity: \(O(V + E)\).

Space complexity: \(O(V + E)\).

Comment on my solution¶

The main issue is that unsafety discovered recursively is not propagated back to the caller.

For example, when exploring 0 -> 1 and node 1 is found unsafe, the caller never checks safe[1] again after dfs(1) returns, so node 0 can incorrectly remain safe.

Additionally:

seen correctly represents the current DFS path, but it does not memoize completed nodes.
Unsafe nodes include nodes that can reach cycles, not only nodes inside cycles.
Starting a fresh DFS from every node can take \(O(V(V + E))\) time.
Recursive DFS can exceed Python's recursion limit for \(10^4\) nodes.

# Ideas:
# - It seems that "not safe" means contains a cycle
#   - So we can try do cycle detection to discard nodes
#     - the complement nodes are then safe nodes

# Wrong Answer: 58/113 testcases passed
# graph = [[1,2,3,4],[1,2,3,4],[3,4],[4],[]]
# Output: [0,2,3,4]
# Expected: [2,3,4]
class Solution:
    def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:
        n = len(graph)
        safe = [True] * n

        def dfs(node):
            seen.add(node)
            for nei in graph[node]:
                if nei in seen or not safe[nei]:
                    safe[node] = False
                    break
                dfs(nei)
            seen.remove(node)

        for node in range(n):
            seen = set()
            dfs(node)

        res = []

        for node in range(n):
            if safe[node]:
                res.append(node)

        return res