DSA Tracker

Visualize

Find Eventual Safe States

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)

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.

Details

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)?

Problem:Find Eventual Safe StatesMedium

Pattern:Topological Sort

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

step 1 / 10

Nodes and their moves

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

Every step in words

Show all 10 steps
  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.
  2. Count the arrows leaving each node: 0 has 2, 1 has 2, 2 has 1, 3 has 1, 4 has 1, 5 has 0. A node with 0 is a dead end already — automatically safe — so that count is the only state worth tracking, same trick as counting arrows IN for a topological sort, just pointed the other way.
  3. Only node 5 has 0 outgoing edges — it is a dead end, so it is safe by definition. Queue it as the one confirmed-safe node to start peeling backward from.
  4. Node 5 comes off the queue with 0 edges outstanding, so mark it SAFE — that is 1 confirmed so far, and the queue is now empty.
  5. Every node that points AT 5 just had one of its own paths confirmed safe, so their counts drop by one: 2 now has 0, 4 now has 0. 2 and 4 reached 0, so they join the queue.
  6. Node 2 comes off the queue with 0 edges outstanding, so mark it SAFE — that is 2 confirmed so far, and 4 still waits.
  7. Every node that points AT 2 just had one of its own paths confirmed safe, so their counts drop by one: 0 now has 1, 1 now has 1. None of them reached 0, so nothing new is confirmed yet.
  8. Node 4 comes off the queue with 0 edges outstanding, so mark it SAFE — that is 3 confirmed so far, and the queue is now empty.
  9. Nothing points at 4, so no other node's count moves.
  10. The queue emptied with 2, 4, 5 confirmed safe, but 0, 1, 3 still carry a count above 0 — the highlighted arrows show why: they only ever lead back into each other, so none of THEM can ever be the one that dead-ends. RETURN [2, 4, 5].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Find Eventual Safe States in the editorAll Graph problemsBack to roadmap