Given a directed graph, return all vertices that are eventual safe states. A node is safe if every possible path starting from it eventually ends at a terminal node and never enters a cycle. Pattern focus: DFS. Use graph coloring or reverse graph reasoning to detect nodes that do not lead into cycles.
graph = adjacency list of a directed graph
sorted list of safe node indices
Example 1:
Input:
graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output:
[2,4]
Explanation:
Nodes 2, 4, 5, and 6 do not lead into a cycle.
Example 2:
Input:
graph = [[1],[2],[0]]
Output:
[]
Explanation:
Every node is part of a directed cycle.
Example 3:
Input:
graph = [[1],[2],[]]
Output:
[0,1]
Explanation:
This graph is acyclic, so every node is safe.