Find Eventual Safe States
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
graph = [[1,2],[2,3],[5],[0],[5],[],[]][2,4,5,6]Nodes 5,6 are terminal (safe). Node 4→5 (safe). Node 2→5 (safe). Nodes 0,1,3 form cycle, unsafe.
graph = [[1],[2],[3],[4],[]][0,1,2,3,4]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.
graph = [[1,3],[2],[0],[1,2]][]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⁴
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.