106. Eventual Safe States
A vertex is safe when every path you could choose from it eventually terminates. Find all vertices for which it is impossible to keep traversing indefinitely.
A vertex with one terminating route and another route into a cycle is not safe. This is an all-paths condition, not merely existence of one safe route.
Example 1
Input
[[1,2],[2,3],[5],[0],[5],[],[]]
Output
[2,4,5,6]
Explanation: The cycle 0→1→3→0 makes those vertices unsafe, even though 1 can also reach terminal 5 via 2.
Example 2
Input
[[1,2],[],[2]]
Output
[1]
Explanation: Vertex 0 can choose the terminal branch, but can also enter the self-loop at 2; safety quantifies over every path.
Example 3
Input
[[1,1],[],[2]]
Output
[0,1]
Explanation: Both duplicate occurrences from 0 are discharged when terminal 1 is removed; self-loop 2 remains blocked.
Constraints
0 <= graph.length <= 1050 <= outgoing edge occurrences <= 2 * 1050 <= neighbor < graph.length
Hints
Hint 1
A terminal is safe without choosing an outgoing edge.
Hint 2
A predecessor becomes safe only after every successor is safe.
Hint 3
Count remaining outgoing occurrences, peel via reverse edges, and collect labels in sorted order.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
A cycle remains despite an optional terminal branch
[[1,2],[2,3],[5],[0],[5],[],[]]
[2,4,5,6]