Show problems as
Classic problem #802MediumDepth-First SearchBreadth-First SearchGraph TheoryTopological SortKosaraju's AlgorithmTarjan's SCC Algorithm

Find Eventual Safe States

Real-world version: States From Which the Batch Always Halts
Tracked in this browser only
Read Find Eventual Safe States on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstCycle Detection · Graphs, animated step by step

A batch machine has n states numbered 0 through n - 1. graph[i] lists, in strictly increasing order, the states the machine may move to in one step from state i. When graph[i] is empty the machine has nowhere to go and stops there; call such a state a stopping state. A state may list itself.

The machine is free to pick any listed move at each step, so a run from a state is any sequence of moves that follows the lists. A state is settled when every run that starts there reaches a stopping state after finitely many steps, no matter which moves are picked along the way. Note that a stopping state is settled.

Return the list of all settled states, in increasing numerical order.

Examples

Example 1

Input
graph = [[1], [2], [1], []]
Output
[3]

State 3 lists no moves, so it is a stopping state and is settled. States 1 and 2 move into each other, so a run between them never stops. State 0 moves to state 1, so its run never stops either.

Example 2

Input
graph = [[0], []]
Output
[1]

State 0 lists itself, so the run from it can go on forever. State 1 lists no moves and is settled.

Example 3

Input
graph = [[1, 2], [], [2]]
Output
[1]

State 1 is a stopping state. State 2 lists only itself, so a run from it never stops. State 0 may move to state 2, and the definition requires every run from a state to stop, so state 0 is not settled.

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.
  • A state may list itself.
  • The total number of moves listed across all states is between 1 and 4 * 10^4.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def eventual_safe_nodes(graph: list[list[int]]) -> list[int]:
Java
public List<Integer> eventualSafeNodes(int[][] graph)

More on the same topics