Find Eventual Safe States Medium 0 attempts
LeetCode ↗

Find Eventual Safe States

Medium GraphBFSDFS LeetCode

Given a directed graph, return all nodes that are eventually safe (all paths from them lead to terminal nodes).

Example: graph = [[1,2],[2,3],[5],[0],[5],[],[]] → Output: [2,4,5,6]

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

Reverse Topological Sort

Terminal nodes have no outgoing edges. Process in reverse — safe nodes are those with all successors safe.

function eventualSafeNodes(graph) {
  const n = graph.length, color = Array(n).fill(0);
  function dfs(u) {
    if (color[u] > 0) return color[u] === 2;
    color[u] = 1;
    for (const v of graph[u]) if (!dfs(v)) return false;
    color[u] = 2;
    return true;
  }
  const result = [];
  for (let i = 0; i < n; i++) if (dfs(i)) result.push(i);
  return result;
}

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

Saved in this browser only. Private to you.

JavaScript