Find Eventual Safe States

easy

Acceptance: 58%

GraphsDFSTopological Sort

In a directed graph of n nodes (0 to n-1), a node is terminal if it has no outgoing edges. A node is safe if every path originating from it eventually reaches a terminal node (i.e., the node is not part of any cycle). Return all safe nodes in ascending order.

Examples

Example 1:

Input:graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output:[2,4,5,6]

Explanation: Nodes 5 and 6 are terminal. Node 4 leads only to 5. Node 2 leads only to 5. Nodes 0, 1, and 3 participate in a cycle and are unsafe.

Example 2:

Input:graph = [[],[0],[1],[2]]

Output:[0,1,2,3]

Explanation: No cycles exist. Node 0 is terminal; all others eventually lead to node 0.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Find Eventual Safe States

Examples

Hints

Related Problems