Find eventual safe states

Hard

Reverse the edges and run Kahn's

Problem

Return all nodes from which every path leads to a terminal node (no cycles reachable).

In simple words

A node is safe if every path from it avoids cycles — DFS colouring detects who lands on a loop.

The idea

A node is safe when every path from it ends at a terminal node, which means it can reach no cycle. Reversing all edges turns terminal nodes into sources, so Kahn's algorithm on the reversed graph emits exactly the safe nodes.

The trick

Reverse the graph; out-degree zero becomes in-degree zero.
Everything Kahn's emits is safe; the rest touch a cycle.
Sort the result — the answer is usually expected in ascending order.

←→stepspaceplay

indegrees[0,1,2,1]

1/6

Optimal

timeO(V+E)spaceO(V+E)

Cycle ⇒ impossible.

1q = every course whose indegree is 02while q not empty:3  c = q.pop(); processed += 14  for nb in adj[c]: indeg[nb] -= 1; if now 0, q.push(nb)5return processed == numCourses

Input

nodes: 4, 4 edges

Memory

indegrees: [0,1,2,1]
processed: —

Output

finish: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output:: [2, 4, 5, 6]
Explanation:: Nodes leading only to terminals are safe.

Example 2

Input:: graph = [[],[0,2,3,4],[3],[4],[]]
Output:: [0, 1, 2, 3, 4]
Explanation:: All nodes avoid cycles here.

Example 3

Input:: graph = [[1],[0]]
Output:: []
Explanation:: A 2-cycle makes both unsafe → none.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.