Given a directed graph, return all safe vertices in increasing order. A vertex is safe if every path starting from it eventually ends at a terminal vertex. Pattern focus: Only valid on DAGs. Reverse topological thinking is often the cleanest way to solve this.
graph = adjacency list of a directed graph
sorted list of safe vertices
Example 1:
Input:
graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output:
[2,4]
Explanation:
Nodes 2, 4, 5, and 6 only reach terminal nodes; the others are part of or lead to a cycle.
Example 2:
Input:
graph = [[]]
Output:
[]
Explanation:
The only node is terminal, so it is safe.
Example 3:
Input:
graph = [[1],[2],[0]]
Output:
[]
Explanation:
Every node is part of the cycle 0 -> 1 -> 2 -> 0.