DSA problem
Find Eventual Safe States
You are given a directed graph with n nodes labeled 0 to n - 1 represented as an adjacency list graph, where graph[i] is the list of nodes reachable in one step from node i. A node is called terminal if it has no outgoing edges. A node is called safe if every possible path starting from that node eventually leads to a terminal node — equivalently, no path from it can revisit a node on the way (no path enters a cycle). Return all safe nodes in ascending order.
Phrased differently, a node is safe iff it is not part of any cycle and cannot reach any cycle. The standard topological-sort framing makes this trivial: reverse every edge of the graph. In the reversed graph, terminal nodes become the only nodes with out-degree zero in the original, which translates to in-degree zero in the reversed graph after the flip, so they are the natural Kahn's sources.
Run Kahn's BFS on the reversed graph. Whenever a node is popped from the queue, it is reachable only through chains of nodes that eventually end at a terminal — i.e. it is a safe node. Push each newly zero-in-degree node onto the queue and mark every popped node as safe. Nodes that remain with non-zero in-degree at the end live inside a cycle or feed into one and so are unsafe.
Finally, scan 0..n - 1 and emit the indices marked safe — they are already returned in ascending order. The whole algorithm runs in O(V + E) time and uses O(V + E) space, optimal for the size of the input graph.
Examples
graph = [[1,2],[2,3],[5],[0],[5],[],[]][2,4,5,6]graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]][4]graph = [[],[0,2,3,4],[3],[4],[]][0,1,2,3,4]Constraints
- n == graph.length
- 1 <= n <= 10^4
- 0 <= graph[i].length <= n
- 0 <= graph[i][j] <= n - 1
- graph[i] is sorted in strictly increasing order.
- The graph may contain self loops.
- The number of edges in the graph will be in the range [1, 4 * 10^4].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.