Standard Bar Graphs · Topo Sort Problems O(V + E) · O(V + E)
A rail dispatcher's one-way junction map must certify which starting junctions are safe: from them, every train, however it chooses its route, eventually rolls into an end-of-line terminal and stops. Junctions that can feed an endless loop — directly or one hop removed — can never be certified, and the dispatcher lists only the safe ones in ascending order.
Input: A directed graph as an adjacency list graph where graph[i] lists the junctions node i points to.
Output: Return every safe node in ascending order.
1 <= n <= 10^40 <= graph[i].length <= n0 <= graph[i][j] < nInput: {"graph":[[1,2],[2,3],[5],[0],[5],[],[]]}
Output: [2,4,5,6]
Nodes 2, 4 and 6 roll straight into terminal 5; node 0, 1 or 3 can drift into the 0-1-3 loop.
Input: {"graph":[[],[0,2],[1]]}
Output: [0]
Node 0 is itself terminal; 1 and 2 chase each other forever.