Find Eventual Safe States
Medium · Graphs · Depth-First Search · Breadth-First Search · Graph · Topological Sort
Problem
You are given a directed graph of n nodes labelled 0 to n - 1, as a list graph where graph[i] lists the nodes that node i has an edge to.
A node is terminal if it has no outgoing edges. A node is safe if every path that starts at it eventually ends at a terminal node; in other words, no path from it can get stuck going around a cycle forever.
Return all safe nodes, sorted in increasing order.
Examples
Input: graph = [[1],[2],[],[0,4],[3]] Output: [0,1,2]
Node 2 is terminal and 0 → 1 → 2 always reaches it; nodes 3 and 4 can loop forever between each other.
Input: graph = [[0],[0,2],[]] Output: [2]
Node 0 has a self-loop, and node 1 can step into node 0, so only the terminal node 2 is safe.
Input: graph = [[],[0],[0,1]] Output: [0,1,2]
The graph has no cycle, so every node is safe.
Constraints
- n == len(graph)
- 1 <= n <= 10^4
- 0 <= len(graph[i]) <= n
- 0 <= graph[i][j] <= n - 1
- graph[i] is sorted in strictly increasing order
- The graph may contain self-loops
- The total number of edges is between 1 and 4 · 10^4
Approaches
- Baseline: look for a reachable cycle from every node — time O(n·(n + e)), space O(n)
Follow-up
Safe nodes form a graph with no cycles, so questions like “how long is the longest walk to a terminal node?” have finite answers on them. See the use cases for that, and for the weaker question “can some path reach a terminal node?”.
Related problems
Start free on Cariara · Coding problems · System design studio
