Pattern visualizer

Find Eventual Safe States

Checking every path from a node would be exponential, but the question is really the opposite of Course Schedule's: instead of counting arrows IN and peeling from the sources, count arrows OUT and peel from the dead ends. A node with 0 outgoing edges is safe for free. Once every node IT points to is confirmed safe, it becomes safe too — so 'confirmed safe' spreads backward along the arrows exactly like 'no prerequisites left' spread forward. Whatever never gets reached is stuck feeding a cycle. Animated on: 6 nodes with moves 0->1, 0->2, 1->2, 1->3, 2->5, 3->0, 4->5 (a->b means a can move to b) — which nodes are eventually safe (every path from them dead-ends)?.

Peel dead ends backward: a node is safe once every node it points to is already safe

time O(V + E)space O(V + E)step 1 / 10

Nodes and their moves

line 1

6 nodes, and an arrow a to b means a can move to b. A node is safe only if EVERY path out of it eventually dead-ends at a node with no outgoing edges — one arrow into a cycle is enough to disqualify it, so the question is which nodes can reach one.

Pseudocode

1FUNCTION eventualSafeNodes(n, edges):
2  FOR EACH (a, b) IN edges
3    APPEND b TO adj[a]
4    APPEND a TO radj[b]
5    outdeg[a] <- outdeg[a] + 1
6  queue <- EVERY u WHERE outdeg[u] = 0
7  WHILE queue NOT EMPTY
8    u <- REMOVE FIRST FROM queue
9    safe[u] <- TRUE
10    FOR EACH p IN radj[u]
11      outdeg[p] <- outdeg[p] - 1
12      IF outdeg[p] = 0
13        APPEND p TO queue
14  RETURN SORT(EVERY u WHERE safe[u])

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap