☕ DSA Java Articles

Topics › Graphs › Topo Sort and Problems

Find eventual safe states

Hard TUF ID 506 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a directed graph of n nodes as an adjacency array: graph[i] lists the nodes that i has edges to. A node is terminal if it has no outgoing edges. A node is safe if every possible path starting from it ends at a terminal node. Return all safe nodes in increasing order.

Constraints: 1 ≤ n ≤ 10^4, 0 ≤ graph[i].length ≤ n, total edges up to 4 × 10^4. The graph may contain self-loops.

Example 1

graph = [[1,2], [2,3], [5], [0], [5], [], []]
answer = [2, 4, 5, 6]
// 5 and 6 are terminal; 2 and 4 lead only to 5.
// 0, 1 and 3 can go round 0 → 1 → 3 → 0 forever.

Example 2

graph = [[1,2,3,4], [1,2], [3,4], [0,4], []]
answer = [4]             // 1 has a self-loop, and 0 → 3 → 0 is a cycle

Reformulation. In a finite graph, a path that never ends must eventually repeat a node, so it runs around a cycle. Therefore a node is unsafe exactly when it can reach a cycle (including a cycle it sits on), and safe otherwise. Note that “some path reaches a terminal” is not enough: in the test [[1, 3], [2], [1], []], node 0 can go straight to terminal 3, but it can also enter the loop 1 ↔ 2, so it is unsafe.

Approach 1: Brute force

Intuition. Test each node separately: run a DFS from it with fresh state and ask whether that DFS ever meets a node that is still on its own path, which is a back edge and therefore a reachable cycle. The DFS is the standard three-state cycle check: 0 new, 1 on the current path, 2 finished with no cycle found below it.

Algorithm.

  1. For each node s, allocate a fresh state array and call reachesCycle(s).
  2. In reachesCycle(u): set state 1; for each neighbour v, return true if v is in state 1, or if v is new and its own call returns true.
  3. Set state 2 and return false.
  4. Nodes for which the call returns false are safe; scanning s in increasing order keeps the output sorted.
static List<Integer> bruteForce(int[][] graph) {
    int n = graph.length;
    List<Integer> safe = new ArrayList<>();
    for (int s = 0; s < n; s++) {
        if (!reachesCycle(s, graph, new int[n])) safe.add(s);
    }
    return safe;
}

/** DFS with states 0 = new, 1 = on current path, 2 = finished. Returns true if a cycle is reachable from u. */
static boolean reachesCycle(int u, int[][] graph, int[] state) {
    state[u] = 1;
    for (int v : graph[u]) {
        if (state[v] == 1) return true;
        if (state[v] == 0 && reachesCycle(v, graph, state)) return true;
    }
    state[u] = 2;
    return false;
}

Complexity. Time O(V × (V + E)): a full DFS from each of the V nodes. Space O(V) per DFS for the state array and recursion. With 10^4 nodes and 4 × 10^4 edges this is around 5 × 10^8 steps, too slow.

Approach 2: DFS with shared state

Intuition. The brute force throws away everything it learns. Keep one state array for the whole graph and reuse the same reachesCycle helper. Two facts make the reuse correct:

After an aborted search, state 1 no longer only means “on the current path”; it can also mean “known to reach a cycle”. Both readings say the same thing to a later search: if you can walk into this node, you can reach a cycle. So the check state[v] == 1 → return true remains correct, and no node is ever expanded twice.

Algorithm.

  1. Allocate one state array.
  2. For each node s in increasing order: if it is new, call reachesCycle(s). Afterwards, s is safe exactly when state[s] == 2.
static List<Integer> dfsShared(int[][] graph) {
    int n = graph.length;
    int[] state = new int[n];
    List<Integer> safe = new ArrayList<>();
    for (int s = 0; s < n; s++) {
        if (state[s] == 0) reachesCycle(s, graph, state);
        if (state[s] == 2) safe.add(s);
    }
    return safe;
}

On Example 1: the call from 0 walks 0 → 1 → 2 → 5, finishes 5 and 2 with state 2, continues 1 → 3 → 0 and finds 0 in state 1. It returns true with 0, 1, 3 left at 1. Later, 2 and 5 are already 2, 4 finishes via 5, and 6 finishes alone, giving [2, 4, 5, 6].

Complexity. Time O(V + E): each node is expanded at most once over the whole run. Space O(V) for the state array plus recursion depth up to V.

Approach 3: Optimal, Kahn’s algorithm on the reversed graph

Intuition. Think about safety from the terminal end. Terminal nodes are safe. A node is safe when all of its outgoing edges lead to safe nodes. That is the same shape as Kahn’s topological sort, with “number of incoming edges not yet removed” replaced by “number of outgoing edges not yet known to be safe”:

A node on a cycle keeps the edge to its successor on that cycle, which is never confirmed, so its count never reaches 0. The same holds for any node with an edge into such a node. So the nodes that are never confirmed are exactly the unsafe ones.

Algorithm.

  1. Build reversed and record outdegree[u] = graph[u].length.
  2. Queue every node with out-degree 0.
  3. Pop v, mark it safe, and for each u in reversed[v] decrement outdegree[u]; queue u when it reaches 0.
  4. Collect safe nodes by scanning indices in order, which gives sorted output without a sort.
static List<Integer> optimal(int[][] graph) {
    int n = graph.length;
    List<List<Integer>> reversed = new ArrayList<>();
    for (int i = 0; i < n; i++) reversed.add(new ArrayList<>());
    int[] outdegree = new int[n];
    for (int u = 0; u < n; u++) {
        outdegree[u] = graph[u].length;
        for (int v : graph[u]) reversed.get(v).add(u);
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (outdegree[i] == 0) queue.add(i);   // terminal nodes are safe
    boolean[] safe = new boolean[n];
    while (!queue.isEmpty()) {
        int v = queue.poll();
        safe[v] = true;
        for (int u : reversed.get(v)) {
            if (--outdegree[u] == 0) queue.add(u);       // every edge of u now leads to a safe node
        }
    }
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; i++) if (safe[i]) result.add(i);
    return result;
}

Dry run on Example 1. Out-degrees for nodes 0..6 are 2, 2, 1, 1, 1, 0, 0. Reversed edges: 5 ← 2, 4; 2 ← 0, 1; 0 ← 3; 1 ← 0; 3 ← 1.

pop marked safe out-degree changes queue after
start     [5, 6]
5 5 node 2: 1 → 0, node 4: 1 → 0 [6, 2, 4]
6 6 none [2, 4]
2 2 node 0: 2 → 1, node 1: 2 → 1 [4]
4 4 none []

Nodes 0, 1 and 3 each keep one unconfirmed edge (along the cycle), so the answer is [2, 4, 5, 6].

Complexity. Time O(V + E): building the reversed graph touches each edge once, and each edge is decremented once. Space O(V + E) for the reversed graph, the degree array and the queue.

Approaches 2 and 3 are both linear. The DFS reuses the cycle-detection pattern directly; the BFS is iterative, so it is safe for long chains, and it makes the “a node is safe when all its edges are safe” rule explicit.

Edge cases and pitfalls