Find Eventual Safe States in a Directed Graph

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.

Understanding the Problem

In this problem, we are given a directed graph represented as an adjacency list. Our goal is to find all the eventual safe states.

An eventual safe state is a node from which any possible path will always lead to a terminal node (a node with no outgoing edges) and never enter a cycle. If a node can reach a cycle, it is not considered safe.

This means we must find all nodes that do not participate in or lead to a cycle in any way.

Step-by-Step Solution with Example

Step 1: Understand the graph structure

Let’s consider the example: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Each index represents a node, and the array at each index lists the nodes it points to. For instance, node 0 points to nodes 1 and 2.

Step 2: Reverse the graph

To track which nodes lead to which, we build a reversed graph. In the reversed graph, for every edge u → v in the original graph, we add an edge v → u.

This helps us track who depends on which node, making it easier to determine when a node becomes safe.

Step 3: Track out-degrees

We maintain an array where outdegree[i] stores the number of outgoing edges from node i in the original graph.

Terminal nodes (with no outgoing edges) will have outdegree 0. These are our starting point — they are trivially safe.

Step 4: Use a queue to process safe nodes

We put all terminal nodes in a queue and process them one by one. For each node removed from the queue, we go through its parents in the reversed graph and reduce their out-degree by 1.

If a parent’s out-degree becomes 0, it also becomes safe, so we add it to the queue.

Step 5: Collect and sort safe nodes

All nodes whose out-degree becomes 0 during this process are eventually safe. We collect them, sort them, and return them as the final answer.

Edge Cases

• Empty graph: If the input graph has no nodes, the result should be an empty list.
• All terminal nodes: If every node has no outgoing edges, all are safe.
• All nodes in a cycle: If every node is part of a cycle, no node is safe.
• Disconnected components: The algorithm handles each component independently. Safe nodes from different components are still detected correctly.

Finally

This problem is best understood by thinking in reverse: instead of finding which nodes can reach terminal states, we ask which nodes can be reached from terminal states without forming a cycle.

By reversing the graph and tracking out-degrees, we simulate a safe-state propagation, slowly marking each node safe once all its paths are known to be safe. This approach ensures an intuitive and efficient solution suitable even for large graphs.

1. Reverse the graph: for each edge u → v, add u to revAdj[v].
2. Initialize an outDegree[] array where each element is the number of outgoing edges from a node in the original graph.
3. Create a queue and enqueue all nodes with outDegree = 0 (terminal nodes).
4. While the queue is not empty:
1. Dequeue a node node.
2. For each neighbor in revAdj[node]:
1. Reduce outDegree[neighbor] by 1.
2. If outDegree[neighbor] == 0, enqueue neighbor.
5. All nodes with outDegree == 0 at the end are safe. Return them sorted.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

void reverseGraph(int V, int adj[][MAX], int revAdj[][MAX], int outDegree[], int size[]) {
    for (int u = 0; u < V; u++) {
        for (int j = 0; j < size[u]; j++) {
            int v = adj[u][j];
            revAdj[v][size[v]++] = u;
            outDegree[u]++;
        }
    }
}

void eventualSafeNodes(int V, int adj[][MAX], int size[]) {
    int revAdj[MAX][MAX] = {0};
    int revSize[MAX] = {0};
    int outDegree[MAX] = {0};
    bool safe[MAX] = {false};
    int queue[MAX], front = 0, rear = 0;

    reverseGraph(V, adj, revAdj, outDegree, size);

    for (int i = 0; i < V; i++) {
        if (outDegree[i] == 0) queue[rear++] = i;
    }

    while (front < rear) {
        int node = queue[front++];
        safe[node] = true;
        for (int j = 0; j < revSize[node]; j++) {
            int neighbor = revAdj[node][j];
            if (--outDegree[neighbor] == 0) {
                queue[rear++] = neighbor;
            }
        }
    }

    printf("Safe Nodes: ");
    for (int i = 0; i < V; i++) {
        if (safe[i]) printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int V = 7;
    int adj[MAX][MAX] = {
        {1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}
    };
    int size[MAX] = {2, 2, 1, 1, 1, 0, 0};

    eventualSafeNodes(V, adj, size);
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> eventualSafeNodes(vector<vector<int>>& adj) {
    int V = adj.size();
    vector<vector<int>> revAdj(V);
    vector<int> outDegree(V, 0);

    for (int u = 0; u < V; ++u) {
        for (int v : adj[u]) {
            revAdj[v].push_back(u);
            outDegree[u]++;
        }
    }

    queue<int> q;
    vector<bool> safe(V, false);
    for (int i = 0; i < V; ++i) {
        if (outDegree[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int node = q.front(); q.pop();
        safe[node] = true;
        for (int neighbor : revAdj[node]) {
            if (--outDegree[neighbor] == 0) q.push(neighbor);
        }
    }

    vector<int> result;
    for (int i = 0; i < V; ++i) {
        if (safe[i]) result.push_back(i);
    }
    return result;
}

int main() {
    vector<vector<int>> adj = {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}};
    vector<int> safeNodes = eventualSafeNodes(adj);
    cout << "Safe Nodes: ";
    for (int node : safeNodes) cout << node << " ";
    cout << endl;
    return 0;
}

from collections import deque

def eventual_safe_nodes(adj):
    V = len(adj)
    rev_adj = [[] for _ in range(V)]
    out_degree = [0] * V

    for u in range(V):
        for v in adj[u]:
            rev_adj[v].append(u)
            out_degree[u] += 1

    queue = deque(i for i in range(V) if out_degree[i] == 0)
    safe = [False] * V

    while queue:
        node = queue.popleft()
        safe[node] = True
        for neighbor in rev_adj[node]:
            out_degree[neighbor] -= 1
            if out_degree[neighbor] == 0:
                queue.append(neighbor)

    return [i for i, val in enumerate(safe) if val]

# Example usage
print("Safe Nodes:", eventual_safe_nodes([[1,2],[2,3],[5],[0],[5],[],[]]))

import java.util.*;

public class SafeNodesFinder {
    public static List<Integer> eventualSafeNodes(List<List<Integer>> adj) {
        int V = adj.size();
        List<List<Integer>> revAdj = new ArrayList<>();
        for (int i = 0; i < V; i++) revAdj.add(new ArrayList<>());
        int[] outDegree = new int[V];

        for (int u = 0; u < V; u++) {
            for (int v : adj.get(u)) {
                revAdj.get(v).add(u);
                outDegree[u]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        boolean[] safe = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (outDegree[i] == 0) queue.offer(i);
        }

        while (!queue.isEmpty()) {
            int node = queue.poll();
            safe[node] = true;
            for (int neighbor : revAdj.get(node)) {
                if (--outDegree[neighbor] == 0) queue.offer(neighbor);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (safe[i]) result.add(i);
        }
        return result;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = Arrays.asList(
            Arrays.asList(1, 2), Arrays.asList(2, 3), Arrays.asList(5),
            Arrays.asList(0), Arrays.asList(5), new ArrayList<>(), new ArrayList<>()
        );
        System.out.println("Safe Nodes: " + eventualSafeNodes(adj));
    }
}

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

  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]) {
      if (--outDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return safe.map((val, i) => val ? i : -1).filter(i => i !== -1);
}

console.log("Safe Nodes:", eventualSafeNodes([[1,2],[2,3],[5],[0],[5],[],[]]));

package main

import (
    "fmt"
)

func eventualSafeNodes(adj [][]int) []int {
    V := len(adj)
    revAdj := make([][]int, V)
    outDegree := make([]int, V)

    for u := 0; u < V; u++ {
        for _, v := range adj[u] {
            revAdj[v] = append(revAdj[v], u)
            outDegree[u]++
        }
    }

    queue := []int{}
    for i := 0; i < V; i++ {
        if outDegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    safe := make([]bool, V)
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        safe[node] = true
        for _, neighbor := range revAdj[node] {
            outDegree[neighbor]--
            if outDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    result := []int{}
    for i, v := range safe {
        if v {
            result = append(result, i)
        }
    }
    return result
}

func main() {
    adj := [][]int{{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}}
    fmt.Println("Safe Nodes:", eventualSafeNodes(adj))
}

fn eventual_safe_nodes(adj: Vec<Vec<usize>>) -> Vec<usize> {
    let V = adj.len();
    let mut rev_adj = vec![vec![]; V];
    let mut out_degree = vec![0; V];

    for (u, neighbors) in adj.iter().enumerate() {
        out_degree[u] = neighbors.len();
        for &v in neighbors {
            rev_adj[v].push(u);
        }
    }

    let mut queue: Vec<usize> = (0..V).filter(|&i| out_degree[i] == 0).collect();
    let mut safe = vec![false; V];

    while let Some(node) = queue.pop() {
        safe[node] = true;
        for &neighbor in &rev_adj[node] {
            out_degree[neighbor] -= 1;
            if out_degree[neighbor] == 0 {
                queue.push(neighbor);
            }
        }
    }

    safe.iter().enumerate()
        .filter(|&(_, &val)| val)
        .map(|(i, _)| i)
        .collect()
}

fn main() {
    let adj = vec![vec![1, 2], vec![2, 3], vec![5], vec![0], vec![5], vec![], vec![]];
    let result = eventual_safe_nodes(adj);
    println!("Safe Nodes: {:?}", result);
}

fun eventualSafeNodes(adj: List<List<Int>>): List<Int> {
    val V = adj.size
    val revAdj = List(V) { mutableListOf<Int>() }
    val outDegree = IntArray(V)

    for (u in 0 until V) {
        for (v in adj[u]) {
            revAdj[v].add(u)
            outDegree[u]++
        }
    }

    val queue = ArrayDeque<Int>()
    val safe = BooleanArray(V)
    for (i in 0 until V) {
        if (outDegree[i] == 0) queue.add(i)
    }

    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        safe[node] = true
        for (neighbor in revAdj[node]) {
            outDegree[neighbor]--
            if (outDegree[neighbor] == 0) queue.add(neighbor)
        }
    }

    return (0 until V).filter { safe[it] }
}

fun main() {
    val adj = listOf(
        listOf(1, 2), listOf(2, 3), listOf(5), listOf(0), listOf(5), listOf(), listOf()
    )
    println("Safe Nodes: ${eventualSafeNodes(adj)}")
}

func eventualSafeNodes(_ adj: [[Int]]) -> [Int] {
    let V = adj.count
    var revAdj = Array(repeating: [Int](), count: V)
    var outDegree = Array(repeating: 0, count: V)

    for (u, neighbors) in adj.enumerated() {
        outDegree[u] = neighbors.count
        for v in neighbors {
            revAdj[v].append(u)
        }
    }

    var queue = [Int]()
    for i in 0..<V {
        if outDegree[i] == 0 {
            queue.append(i)
        }
    }

    var safe = Array(repeating: false, count: V)
    while !queue.isEmpty {
        let node = queue.removeFirst()
        safe[node] = true
        for neighbor in revAdj[node] {
            outDegree[neighbor] -= 1
            if outDegree[neighbor] == 0 {
                queue.append(neighbor)
            }
        }
    }

    return (0..<V).filter { safe[$0] }
}

let adj = [[1,2],[2,3],[5],[0],[5],[],[]]
print("Safe Nodes:", eventualSafeNodes(adj))

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

  for (let u = 0; u < V; u++) {
    for (const v of adj[u]) {
      revAdj[v].push(u);
      outDegree[u]++;
    }
  }

  const queue: number[] = [];
  const safe: boolean[] = Array(V).fill(false);

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

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

  return safe.map((val, i) => val ? i : -1).filter(i => i !== -1);
}

console.log("Safe Nodes:", eventualSafeNodes([[1,2],[2,3],[5],[0],[5],[],[]]));

Time complexity

Space complexity

O(V + E)

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