Find Eventual Safe States Using Topological Sort (BFS)

Problem Statement❯

In a directed graph with V vertices and E edges (represented as an adjacency list adj), each node is uniquely labeled from 0 to V - 1.

A node is called a terminal node if it has no outgoing edges. A node is a safe node if every possible path starting from that node eventually leads to a terminal node.

The task is to return a sorted list of all such safe nodes.

Examples❯

Adjacency List	Safe Nodes	Description
[[1,2],[2,3],[5],[0],[5],[],[]]	[2,4,5,6]	Only nodes that lead to terminal nodes (5 and 6) are safe
[[],[0,2,3,4],[3],[4],[]]	[0,1,2,3,4]	All nodes lead to terminal node 0 or 4
[[1],[2],[0]]	[]	Cycle exists, no node is safe
[[],[],[]]	[0,1,2]	All nodes are terminal and hence safe
[[],[0],[1]]	[0,1,2]	Each node leads to a terminal node

Solution❯

Understanding the Problem

An eventual safe state in a directed graph is a node from which no cycle can be reached. In other words, if you start from this node and follow any path, you'll always end up at a terminal node (one with no outgoing edges) eventually.

Key Idea: Reverse Graph and Out-Degree Tracking

To detect such states efficiently, we reverse the graph. So instead of tracking which nodes we can go to, we look at who can reach us. We also maintain a count of outgoing edges (out-degree) for each node in the original graph.

Step-by-Step Logic

We start by collecting all terminal nodes (those with 0 out-degree) into a queue. These are trivially safe because there's nowhere to go from them.

Now, for each node we remove from the queue, we look at all nodes that point to it in the reversed graph. For each such node, we reduce their out-degree, as one of their outgoing edges now leads to a known safe node. If their out-degree reaches 0, they also become safe and are added to the queue.

Why This Works

If a node has an eventual path that leads to a cycle, its out-degree will never reach 0 — because at least one path keeps looping. Only nodes that can resolve all their paths into terminal nodes will have their out-degree reduced to zero eventually.

Examples

Case with no cycles: Every node eventually leads to a terminal node, so all nodes are safe.
Case with isolated cycle: Any node in or pointing to the cycle will never be safe.
Edge case - empty graph: No nodes to process, so return an empty list.

Final Result

Once the process finishes, we collect all nodes whose out-degree is 0. These are the safe states. Sorting the result ensures a consistent output format.

Algorithm Steps❯

Reverse the graph: for each edge u → v, add u to revAdj[v].
Initialize an outDegree[] array where each element is the number of outgoing edges from a node in the original graph.
Create a queue and enqueue all nodes with outDegree = 0 (terminal nodes).
While the queue is not empty:

Dequeue a node node.
For each neighbor in revAdj[node]:

Reduce outDegree[neighbor] by 1.
If outDegree[neighbor] == 0, enqueue neighbor.

All nodes with outDegree == 0 at the end are safe. Return them sorted.

Code

JavaScript

function eventualSafeNodes(adj) {
  const V = adj.length;
  const revAdj = Array.from({ length: V }, () => []);
  const outDegree = Array(V).fill(0);

  // Step 1: Build reversed graph and count out-degrees
  for (let u = 0; u < V; u++) {
    for (const v of adj[u]) {
      revAdj[v].push(u);
      outDegree[u]++;
    }
  }

  const queue = [];
  for (let i = 0; i < V; i++) {
    if (outDegree[i] === 0) queue.push(i);
  }

  const safe = Array(V).fill(false);

  while (queue.length) {
    const node = queue.shift();
    safe[node] = true;
    for (const neighbor of revAdj[node]) {
      outDegree[neighbor]--;
      if (outDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  const result = [];
  for (let i = 0; i < V; i++) {
    if (safe[i]) result.push(i);
  }
  return result;
}

// Example usage:
console.log(eventualSafeNodes([[1,2],[2,3],[5],[0],[5],[],[]])); // Output: [2,4,5,6]

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	Even in the best case (e.g., an acyclic graph), we must traverse all vertices and edges to identify safe nodes.
Average Case	O(V + E)	Each node and edge is visited once, whether it's part of a cycle or not.
Worst Case	O(V + E)	In graphs with deep chains or many dependencies, the traversal still touches all vertices and edges once.

Space Complexity❯

O(V + E)

Explanation: We store the reversed adjacency list, out-degree array, and queue, all of which depend on the number of vertices and edges.

⬅ Previous TopicCourse Schedule 2 - Task Ordering Using Topological Sort

Next Topic ⮕Alien Dictionary Character Order