The machine must list every node from which all paths lead eventually to a terminal node — one with zero outgoing edges. A node whose paths can wander forever (into a cycle) is not safe, even if some branches escape.
The key insight is that a node is safe exactly when it is not on any cycle and cannot reach one. The reverse-graph peeling used in topological sort finds the acyclic remainder: repeatedly remove nodes with zero outgoing edges in the original graph (zero incoming in the reversed one), and whatever is stripped is safe. Nodes never stripped are on or leading into cycles.
The approach has three steps. First, build the reverse adjacency list and compute out-degrees on the original graph. Second, seed a queue with all zero-out-degree nodes, pop nodes, decrement the out-degree of every node pointing at the popped one, and enqueue any neighbor whose out-degree hits zero. Third, collect all peeled nodes — they are safe — and return them sorted ascending, as required. Time is O(V + E) and space is O(V + E).
The trickiest edge case is a node that can reach a cycle but is not on it: it never gets peeled because its path leads into an unpeeled cycle, and the machine must exclude it. Terminal nodes themselves are always safe and must appear in the output.
from collections import deque
def eventualSafeNodes(graph):
n = len(graph)
reverse = [[] for _ in range(n)]
outdegree = [0] * n
for u in range(n):
for v in graph[u]:
reverse[v].append(u)
outdegree[u] += 1
q = deque(i for i in range(n) if outdegree[i] == 0)
safe = []
while q:
node = q.popleft()
safe.append(node)
for prev in reverse[node]:
outdegree[prev] -= 1
if outdegree[prev] == 0:
q.append(prev)
return sorted(safe)