#802
Find Eventual Safe States
pupil · 560 · lc medium +28 · verified · 70.3% accepted · 6,980 likes · top 79%
Description
A directed graph of n nodes, labeled 0 through n - 1, is represented as a 0-indexed 2D array graph where graph[i] lists all nodes adjacent to node i (i.e., there is a directed edge from i to each node in graph[i]).
A node with no outgoing edges is a terminal node. A node is safe if every path originating from it leads exclusively to terminal nodes (or other safe nodes).
Return a sorted list of all safe nodes in the graph.
Example 1:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.
Example 2:
Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation:
Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.
Code
1
2
3