Find Eventual Safe States Medium 0 attempts
LeetCode ↗

Find Eventual Safe States

Medium GraphBFSDFS LeetCode

You're given a directed graph. A node with no outgoing edges is called a terminal node, and a node is eventually safe if following any path from it always eventually reaches a terminal node — meaning it can never be part of an endless cycle. Return the list of all eventually safe nodes.

Input Format
Implement eventualSafeNodes(graph). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output
[2,4,5,6]

Example 2

Input
graph = [[0],[]]
Output
[1]
Constraints
  • 1 <= n <= 10^4
  • 0 <= graph[i].length <= n
Test Cases (2)
Case 1
Args: [[[1,2],[2,3],[5],[0],[5],[],[]]] Expected: [2,4,5,6]
Case 2
Args: [[[0],[]]] Expected: [1]
Topics
GraphBFSDFS

Reverse Topological Elimination

Start with terminal vertices. Remove their incoming edges in the reversed graph; a predecessor is safe when every outgoing edge has been removed. Vertices trapped in or leading to cycles are never eliminated.

javascript
function eventualSafeNodes(graph) {
  const n=graph.length,reverse=Array.from({length:n},()=>[]),degree=graph.map(a=>a.length),queue=[];
  graph.forEach((edges,u)=>edges.forEach(v=>reverse[v].push(u)));
  for(let u=0;u<n;u++)if(degree[u]===0)queue.push(u);
  for(let head=0;head<queue.length;head++)for(const u of reverse[queue[head]])if(--degree[u]===0)queue.push(u);
  return degree.flatMap((d,u)=>d===0?[u]:[]);
}

Time: O(V + E) | Space: O(V + E)

Saved in this browser only. Private to you.

JavaScript