195. Eventual Safe Nodes

Why this mechanism works

Start with terminal vertices, whose safety is immediate. Reverse edges to notify predecessors whenever a successor becomes safe. A predecessor becomes safe only after every outgoing edge leads to a confirmed safe vertex. This is elimination by remaining outgoing risk, rather than ordinary incoming prerequisites.

State and boundaries

remaining[u] counts outgoing edges to successors not yet removed as safe. reverse[v] lists predecessors to notify when v is removed.

Protocol

1. Build reverse edges and outgoing counts.
2. Queue all terminal vertices.
3. Mark each removed vertex safe.
4. Decrement each predecessor's remaining count.
5. Queue a predecessor when its count reaches zero.
6. Return marked indices in ascending order.

Visualization

0 -> 1 -> 1   unsafe cycle and its predecessor
2 -> 3        terminal 3 is safe, then 2 becomes safe
output [2,3]

Python implementation

from collections import deque

def safe_nodes(adj):
    reverse = [[] for _ in adj]
    remaining = [len(neighbors) for neighbors in adj]
    for u, neighbors in enumerate(adj):
        for v in neighbors:
            reverse[v].append(u)
    queue = deque(u for u, degree in enumerate(remaining) if degree == 0)
    safe = [False] * len(adj)
    while queue:
        v = queue.popleft()
        safe[v] = True
        for u in reverse[v]:
            remaining[u] -= 1
            if remaining[u] == 0:
                queue.append(u)
    return [u for u in range(len(adj)) if safe[u]]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 safe_nodes: reverse = [[] for _ in adj]
adj=[[1], [1], [3], []]; _=[1]

L4 safe_nodes: reverse = [[] for _ in adj]
adj=[[1], [1], [3], []]; _=[3]

L4 safe_nodes: reverse = [[] for _ in adj]
adj=[[1], [1], [3], []]; _=[]

L4 safe_nodes: reverse = [[] for _ in adj]
adj=[[1], [1], [3], []]; reverse=[[], [], [], []]

L5 safe_nodes: remaining = [len(neighbors) for neighbors in adj]
adj=[[1], [1], [3], []]; reverse=[[], [], [], []]; neighbors=[1]

L5 safe_nodes: remaining = [len(neighbors) for neighbors in adj]
adj=[[1], [1], [3], []]; reverse=[[], [], [], []]; neighbors=[3]

L5 safe_nodes: remaining = [len(neighbors) for neighbors in adj]
adj=[[1], [1], [3], []]; reverse=[[], [], [], []]; neighbors=[]

L5 safe_nodes: remaining = [len(neighbors) for neighbors in adj]
adj=[[1], [1], [3], []]; reverse=[[], [], [], []]; remaining=[1, 1, 1, 0]

... 24 intermediate state changes omitted ...

L18 safe_nodes: return [u for u in range(len(adj)) if safe[u]]
adj=[[1], [1], [3], []]; reverse=[[], [0, 1], [], [2]]; remaining=[1, 1, 0, 0]; neighbors=[]; u=1; v=2; queue=deque([]); safe=[False, False, True, True]

L18 safe_nodes: return [u for u in range(len(adj)) if safe[u]]
adj=[[1], [1], [3], []]; reverse=[[], [0, 1], [], [2]]; remaining=[1, 1, 0, 0]; neighbors=[]; u=2; v=2; queue=deque([]); safe=[False, False, True, True]

L18 safe_nodes: return [u for u in range(len(adj)) if safe[u]]
adj=[[1], [1], [3], []]; reverse=[[], [0, 1], [], [2]]; remaining=[1, 1, 0, 0]; neighbors=[]; u=3; v=2; queue=deque([]); safe=[False, False, True, True]

L18 safe_nodes: return [u for u in range(len(adj)) if safe[u]]
adj=[[1], [1], [3], []]; reverse=[[], [0, 1], [], [2]]; remaining=[1, 1, 0, 0]; neighbors=[]; u=2; v=2; queue=deque([]); safe=[False, False, True, True]

L4 safe_nodes: reverse = [[] for _ in adj]
adj=[[1, 2], [], [2]]; _=[1, 2]

L4 safe_nodes: reverse = [[] for _ in adj]
adj=[[1, 2], [], [2]]; _=[]

L4 safe_nodes: reverse = [[] for _ in adj]
adj=[[1, 2], [], [2]]; _=[2]

L4 safe_nodes: reverse = [[] for _ in adj]
adj=[[1, 2], [], [2]]; reverse=[[], [], []]

L5 safe_nodes: remaining = [len(neighbors) for neighbors in adj]
adj=[[1, 2], [], [2]]; reverse=[[], [], []]; neighbors=[1, 2]

L5 safe_nodes: remaining = [len(neighbors) for neighbors in adj]
adj=[[1, 2], [], [2]]; reverse=[[], [], []]; neighbors=[]

L5 safe_nodes: remaining = [len(neighbors) for neighbors in adj]
adj=[[1, 2], [], [2]]; reverse=[[], [], []]; neighbors=[2]

L5 safe_nodes: remaining = [len(neighbors) for neighbors in adj]
adj=[[1, 2], [], [2]]; reverse=[[], [], []]; remaining=[2, 0, 1]

... 16 intermediate state changes omitted ...

L15 safe_nodes: remaining[u] -= 1
adj=[[1, 2], [], [2]]; reverse=[[], [0], [0, 2]]; remaining=[1, 0, 1]; neighbors=[2]; u=0; v=1; queue=deque([]); safe=[False, True, False]

L18 safe_nodes: return [u for u in range(len(adj)) if safe[u]]
adj=[[1, 2], [], [2]]; reverse=[[], [0], [0, 2]]; remaining=[1, 0, 1]; neighbors=[2]; u=1; v=1; queue=deque([]); safe=[False, True, False]

L18 safe_nodes: return [u for u in range(len(adj)) if safe[u]]
adj=[[1, 2], [], [2]]; reverse=[[], [0], [0, 2]]; remaining=[1, 0, 1]; neighbors=[2]; u=2; v=1; queue=deque([]); safe=[False, True, False]

L18 safe_nodes: return [u for u in range(len(adj)) if safe[u]]
adj=[[1, 2], [], [2]]; reverse=[[], [0], [0, 2]]; remaining=[1, 0, 1]; neighbors=[2]; u=0; v=1; queue=deque([]); safe=[False, True, False]

Why the solution is correct

Terminals are safe. If all successors are safe, every path from their predecessor takes one edge into a terminating path, so it too is safe. Vertices left over each retain a successor in the remainder; repeatedly following those successors reaches a cycle. Thus the eliminated set is exactly the safe set.

Time and space

O(V+E) time and space, including the final ascending index scan.

Common mistakes

One safe successor is insufficient because the definition quantifies over every path. Incoming degree measures a different property.

Reasoning card

Transfer exercise

Explain how three-state DFS can classify safety, and distinguish a current-path marker from a permanently unsafe result.