Find Eventual Safe States
A directed graph has n nodes numbered from 0 to n - 1. It is given as an adjacency list: graph[i] lists every node that node i has an edge to.
A node is terminal if it has no outgoing edges. A node is safe if every possible walk starting from it, whichever edges it follows, ends at a terminal node. Terminal nodes are safe. A node from which you could keep walking forever is not.
Return every safe node, sorted in increasing order.
Constraints
1 <= n <= 10^4graph[i]is sorted in strictly increasing order (no repeated edges) and may containiitself (a self-loop)- The total number of edges is at most
4 * 10^4
Examples
Example 1
Input: graph = [[1],[2],[3],[],[5],[4],[0,4]] Output: [0,1,2,3]
0 → 1 → 2 → 3 ends at 3, which has no outgoing edges, so 0 to 3 are safe. 4 and 5 point at each other forever. 6 has an edge into that loop, so it is unsafe.
Example 2
Input: graph = [[1],[0],[3],[]] Output: [2,3]
0 and 1 form a loop. 2 can only go to 3, a terminal node, so 2 and 3 are safe.
Example 3
Input: graph = [[0]] Output: []
Node 0 has an edge to itself, so a walk from it never has to stop: it isn't safe.
JavaScript you'll use: Graphs and grids in JavaScript Stacks, queues and deques
/**
* @param {number[][]} graph
* @return {number[]}
*/
function eventualSafeNodes(graph) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.