Description
Given a directed graph, find all safe nodes. A safe node has all paths leading to terminal nodes (no outgoing edges) or other safe nodes.
Examples
Input:
graph = [[1,2],[2,3],[5],[0],[5],[],[]]Output:
[2,4,5,6]Explanation:
Safe nodes.
Input:
graph = [[1],[2],[3],[4],[]]Output:
[4]Explanation:
This is a simple linear chain: 0→1→2→3→4. Node 4 is terminal (no outgoing edges) so it's safe. Nodes 0,1,2,3 all eventually lead to cycles when trying to find safe paths, making them unsafe. Only node 4 leads to a terminal state.
Input:
graph = [[1,3],[2],[0],[1,2]]Output:
[]Explanation:
This graph contains cycles: 0→1→2→0 forms a cycle, and node 3 connects to nodes 1 and 2 which are part of the cycle. Since all nodes either participate in cycles or lead to cycles, there are no safe nodes. No node leads to a guaranteed terminal state.
Constraints
- •
1 ≤ n ≤ 10⁴