1062. Find Eventual Safe States

Given a directed graph as an adjacency list 'graph' (graph[i] lists nodes reachable from i in one step), a node is safe if every path starting from it leads to a terminal node (one with no outgoing edges) — that is, it cannot reach a cycle. Return all safe nodes sorted in ascending order. The input is JSON {graph}.

Input: JSON {graph}.

Output: Array — the sorted safe nodes.

Examples

Input: {"graph":[[1,2],[2,3],[5],[0],[5],[],[]]}
Output: [2,4,5,6]
Explanation: These nodes avoid all cycles.

Input: {"graph":[[]]}
Output: [0]
Explanation: A terminal node is safe.

Input: {"graph":[[1],[0]]}
Output: []
Explanation: Both are in a cycle.

Constraints

• 1<=n<=10^4
• directed

Asked by