The contract says every possible walk must stop. One remaining choice into a cycle is enough to make the starting node unsafe.

Reverse edges so each safe node can notify its original predecessors. remaining[u] counts outgoing edges whose destination has not yet been removed as safe. A terminal starts with zero. Each safe removal decrements the corresponding predecessor counts; reaching zero proves all choices safe. Nodes in or leading to cycles never completely disappear. On a finite graph, an infinite walk must revisit a node and therefore contain a cycle, so this exactly separates safe and unsafe starts.

What the function promises: graph is a finite directed adjacency list. Return all safe node labels in increasing order. Empty and disconnected graphs are allowed.

from collections import deque

def safe_nodes(graph):
    n = len(graph)
    predecessors = [[] for _ in range(n)]
    remaining = [len(neighbors) for neighbors in graph]
    for u, neighbors in enumerate(graph):
        for v in neighbors:
            predecessors[v].append(u)
    ready = deque(u for u in range(n) if remaining[u] == 0)
    safe = [False] * n
    while ready:
        u = ready.popleft()
        safe[u] = True
        for parent in predecessors[u]:
            remaining[parent] -= 1
            if remaining[parent] == 0:
                ready.append(parent)
    return [u for u in range(n) if safe[u]]

assert safe_nodes([[1,2], [], [2]]) == [1]
assert safe_nodes([[1], [2], []]) == [0,1,2]
assert safe_nodes([]) == []

Work and storage: O(V+E) time and space. Producing output by scanning labels avoids an extra sorting cost.

When to recognize it: Terminal nodes are safe. A predecessor becomes safe after all its outgoing choices are known safe.

Check before applying it: One path to an exit is not enough. Another choice might enter a cycle and continue forever.

Run ordinary reachability from exits over reversed edges. The first reached safe continuation is enough for this existential question. Requiring all outgoing choices would solve the wrong problem.