Stations From Which You Can Never Get Trapped
Implement safeStations
A rail network has n stations connected by one-way tracks, given as an adjacency list of a directed graph. A terminal station has no outgoing track. A station is safe when every possible route that starts there is guaranteed to reach a terminal station; if some route can circle forever, the station is unsafe. List all safe stations in increasing order.
Unsafe stations are exactly those that can reach a circuit, so a depth-first search that remembers which stations are on the current path can label them all in one pass.
Example 1:
Input: graph = [[1],[2],[0],[0,4],[5],[],[4,5]]
Output: [4,5,6]
Example 2:
Input: graph = [[1],[2],[0]]
Output: []
Example 3:
Input: graph = [[],[0],[1]]
Output: [0,1,2]
+ 15 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 10 stations numbered 0 … n-1; graph[u] lists, in increasing order, every station v reachable from u by a one-way track (adjacency-list form of a directed graph) - ●
A terminal station has no outgoing track; a station may also have a track to itself - ●
A station is safe when EVERY route that starts there ends at a terminal station after finitely many steps (no route can circle forever) - ●
Return all safe stations in increasing order (an empty list if there are none)
graph =