mediumGraphsPure DSA~30 min
Pipeline Stages That Always Terminate
In a directed pipeline graph, a stage is safe if every path leaving it eventually ends at a terminal stage (no outgoing edges) rather than looping forever. List all safe stages.
Problem
Given a directed graph of n nodes (0..n-1) as graph where graph[i] lists i's out-neighbors, a node is safe if every walk starting there reaches a terminal node. Return all safe nodes in ascending order.
Input
An adjacency list graph of out-edges.
Output
A sorted list of safe node ids.
Constraints
- 1 <= n <= 10^4
- 0 <= sum(graph[i].length) <= 4*10^4
- The graph may contain cycles and self-loops.
Examples
Example 1
Input
graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output
[2,4,5,6]
Nodes 5 and 6 are terminal; 2 and 4 only reach terminals; 0,1,3 sit on a cycle.
Example 2
Input
graph = [[],[0,2,3,4],[3],[4],[]]
Output
[0,1,2,3,4]
There is no cycle, so every node is safe.