Routes That Always End

Medium

A text adventure has n screens numbered 0 to n - 1. The list links[i] holds the screens you can move to from screen i. A screen with no links is an ending. Call a screen reliable if a player who starts there is bound to reach an ending, whatever choices they make. In other words, there is no way to get stuck in a cycle from a reliable screen. Endings themselves are reliable. Return the numbers of all reliable screens in ascending order.

Example 1

links=[[1], [2], [], [0, 4], [3]] → [0, 1, 2]

From 0 the walk 0 → 1 → 2 stops at the dead end 2. From 3 you can go to 4 and back to 3 forever, so 3 and 4 do not qualify.

Example 2

links=[[0], [2], []] → [1, 2]

Screen 0 links to itself, so a player can loop there forever. Screens 1 and 2 always reach an ending.

Example 3

links=[[1, 2], [2], [1]] → []

Constraints

1 ≤ n = len(links) ≤ 10⁴
0 ≤ links[i][j] ≤ n - 1
Each links[i] is strictly increasing (a screen may link to itself)
At most 4·10⁴ links in total

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Topological Sort

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Best Roots for a Tree Medium Longest Hike Through the Woods Medium Does This Step Come First Medium

Input

links=[[1], [2], [], [0, 4], [3]]

Expected

[0, 1, 2]

Run checks the first 3 tests in your browser. Submit checks all 59 tests on the server, hidden ones included.