Find Eventual Safe States

medium graph dfs topological sort

Problem

A directed graph is given as adjacency lists. A node is safe if every path starting from it leads to a terminal node (one with no outgoing edges). Return the sorted list of safe nodes.

Inputgraph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output[2, 4, 5, 6]

5 and 6 are terminals; 2 → 5 and 4 → 5 are safe; 0, 1, 3 sit on a 0→1→3→0 cycle.

adjacency (rows ;, neighbors ,)

def eventual_safe_nodes(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(graph)
    def dfs(u):
        if color[u] != WHITE:
            return color[u] == BLACK
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == BLACK:
                continue
            if color[v] == GRAY or not dfs(v):
                return False
        color[u] = BLACK
        return True
    return [i for i in range(len(graph)) if dfs(i)]

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

class Solution {
    int[] color;
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        color = new int[n];
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < n; i++) if (dfs(graph, i)) out.add(i);
        return out;
    }
    private boolean dfs(int[][] g, int u) {
        if (color[u] != 0) return color[u] == 2;
        color[u] = 1;
        for (int v : g[u]) {
            if (color[v] == 2) continue;
            if (color[v] == 1 || !dfs(g, v)) return false;
        }
        color[u] = 2;
        return true;
    }
}

class Solution {
public:
    vector<int> color;
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        color.assign(n, 0);
        vector<int> out;
        for (int i = 0; i < n; i++) if (dfs(graph, i)) out.push_back(i);
        return out;
    }
    bool dfs(vector<vector<int>>& g, int u) {
        if (color[u] != 0) return color[u] == 2;
        color[u] = 1;
        for (int v : g[u]) {
            if (color[v] == 2) continue;
            if (color[v] == 1 || !dfs(g, v)) return false;
        }
        color[u] = 2;
        return true;
    }
};

Explanation

A node is safe only if every path leaving it eventually dead-ends at a node with no outgoing edges — meaning it can never get stuck going around a cycle. The clever way to test this is a single DFS with three colors.

We paint each node one of three colors: WHITE means not visited yet, GRAY means it is currently on the DFS path (in the recursion stack), and BLACK means fully explored and confirmed safe. When we visit a node we mark it GRAY, then recurse into all its neighbors.

The key rule: if we ever reach a neighbor that is still GRAY, we have looped back onto our own path, so a cycle exists and the node is not safe. If a neighbor is BLACK it is already safe, so we skip it. Only if every neighbor turns out safe do we paint the current node BLACK and return True.

Example: with graph = [[1,2],[2,3],[5],[0],[5],[],[]], nodes 5 and 6 have no edges, so they are terminals and instantly safe. Node 2 only points to 5, so it is safe too. But 0 → 1 → 3 → 0 forms a cycle, so those three stay unsafe.

Finally we collect every index whose DFS returned True, giving the sorted list [2, 4, 5, 6]. Each node is colored once, so the whole scan is linear in nodes plus edges.

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