Safe States

Time: O(V+E)

Space: O(V+E)

Intuition

A node is safe if all paths from it eventually lead to a terminal node (no cycle reachable). Use reverse graph + topological sort or DFS coloring.

Algorithm

1DFS with colors: white(0), gray(in-progress), black(safe).
2If node is gray when revisited: cycle ? not safe. If black: safe.
3Color each node after DFS as black (safe) if no cycle found.

Common Pitfalls

•A node is safe if it's not on a cycle and doesn't lead to a cycle. Coloring: gray=visiting, black=confirmed safe.

Safe States.java

Java

// Approach: Reverse graph, then topological sort / BFS from terminal nodes. Safe = reachable from terminal.
// Time: O(V+E) Space: O(V+E)
import java.util.*;

class Solution {
    public ArrayList<Integer> safeNodes(int V, int[][] edges) {
        ArrayList<ArrayList<Integer>> revGraph = new ArrayList<>();
        int[] outdeg = new int[V];
        for (int i = 0; i < V; i++)
            revGraph.add(new ArrayList<>());
            
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            revGraph.get(v).add(u);
            outdeg[u]++;
        }

        Queue<Integer> q = new LinkedList<>();
        ArrayList<Integer> safe = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (outdeg[i] == 0)
                q.add(i);
        }

        while (!q.isEmpty()) {
            int node = q.poll();
            safe.add(node);

            for (int parent : revGraph.get(node)) {
                outdeg[parent]--;
                if (outdeg[parent] == 0)
                    q.add(parent);
            }
        }
        Collections.sort(safe);

        return safe;
    }
}

Was this solution helpful?