Find Eventual Safe States

The most direct way to check if a node is safe: start at that node, and explore every possible path from it. If all paths eventually reach a terminal node, the node is safe. If any path leads back to a node already on the current path (forming a cycle), the node is unsafe.

Imagine you are at the entrance of a maze. You want to know: "No matter which turns I take, will I always reach an exit?" The brute force answer is to try every combination of turns. If even one sequence of turns leads you in a circle, you declare the entrance unsafe.

Concretely, for each node, we run a Depth-First Search (DFS) with a path-visited set that tracks which nodes are on our current path. If DFS from a node revisits any node on the current path, we have found a cycle and the starting node is unsafe.

The critical problem with this approach is that we check each node independently, without remembering results from previous checks. If node 0's DFS already determined that node 2 leads to a terminal, we forget that fact when later checking node 1 (which also goes through node 2). This leads to massive redundant computation.

Let's trace with graph = [[1,2],[2,3],[5],[0],[5],[],[]].

Check node 0:

• Start DFS from 0. pathVisited = {0}
• Visit neighbor 1. pathVisited = {0, 1}
• Visit neighbor 2 (of node 1). pathVisited = {0, 1, 2}
• Visit neighbor 5 (of node 2). pathVisited = {0, 1, 2, 5}
• Node 5 has no neighbors → terminal → this path is safe. Backtrack.
• Back at node 1, visit neighbor 3. pathVisited = {0, 1, 3}
• Visit neighbor 0 (of node 3). But 0 is ALREADY in pathVisited! Cycle detected: 0→1→3→0
• Node 0 is unsafe. ❌

Check node 1:

• Start fresh DFS from 1. pathVisited = {1}
• Visit neighbor 2. pathVisited = {1, 2}
• Visit neighbor 5 (of node 2). Terminal → safe path. Backtrack.
• Visit neighbor 3 (of node 1). pathVisited = {1, 3}
• Visit neighbor 0 (of node 3). pathVisited = {1, 3, 0}
• Visit neighbor 1 (of node 0). But 1 is in pathVisited! Cycle: 1→3→0→1
• Node 1 is unsafe. ❌
• Notice: we re-explored nodes 2 and 5 even though we already knew they were safe from checking node 0. This is the wasted work.

Check node 2:

• Start fresh DFS from 2. pathVisited = {2}
• Visit neighbor 5. Terminal → all paths from 2 are safe.
• Node 2 is safe. ✅

Check node 3:

• Start fresh DFS from 3. pathVisited = {3}
• Visit neighbor 0. pathVisited = {3, 0}
• Visit neighbor 1 (of node 0). pathVisited = {3, 0, 1}
• Visit neighbor 3 (of node 1). But 3 is in pathVisited! Cycle: 3→0→1→3
• Node 3 is unsafe. ❌

Check node 4:

• Start fresh DFS from 4. pathVisited = {4}
• Visit neighbor 5. Terminal → safe.
• Node 4 is safe. ✅

Check node 5: Terminal (no neighbors). Trivially safe. ✅

Check node 6: Terminal (no neighbors). Trivially safe. ✅

Result: [2, 4, 5, 6]

We ran 7 independent DFS traversals. Nodes 2, 5 were explored during checks for 0, 1, 2, and 3 — that's 4 redundant explorations of the same subgraph.

1. For each node i from 0 to n-1:
   a. Create a fresh pathVisited set
   b. Run isSafe(graph, i, pathVisited)
   c. If safe, add i to the result list
2. In isSafe(node, pathVisited):
   a. If node is in pathVisited → cycle detected → return false
   b. If graph[node] is empty → terminal → return true
   c. Add node to pathVisited
   d. For each neighbor of node:
   • If isSafe(neighbor, pathVisited) returns false → return false
     e. Remove node from pathVisited (backtrack)
     f. Return true
3. Return the result list (already sorted since we iterate 0 to n-1)

Time Complexity: O(V × (V + E))

For each of the V nodes, we run a fresh DFS that can visit up to V nodes and traverse up to E edges. Without memoization, the same subgraphs are re-explored for different starting nodes. In pathological cases with many overlapping paths, this can degrade further.

Space Complexity: O(V)

The inPath set (or boolean array) uses O(V) space. The recursion stack can be at most V deep. Each DFS call uses a fresh set, so total space per DFS is O(V).

With n up to 10^4 and edges up to 4 × 10^4, the worst case is approximately 10^4 × (10^4 + 4 × 10^4) = 5 × 10^8 operations — far too slow for typical time limits of 1-2 seconds.

Instead of running independent DFS calls per node, we use a single DFS pass over the entire graph with a clever coloring scheme that simultaneously detects cycles and caches safety results.

Imagine each node starts as a white blank page. When we begin exploring a node, we color it gray ("currently investigating — do not disturb"). When we finish exploring all of its paths and confirm they are all safe, we color it black ("confirmed safe — case closed").

The magic: if during DFS we encounter a gray node, it means we have returned to a node that is currently being investigated — we have found a cycle. The gray node is on the current DFS recursion stack, so we've come full circle. The entire chain of gray nodes involved in this cycle is unsafe.

If we encounter a black node, we already know it is safe, so we can skip it immediately. If we encounter a white node, it hasn't been investigated yet, so we recurse into it.

This three-color scheme achieves two goals simultaneously:

1. Cycle detection: Gray nodes on the recursion stack reveal cycles
2. Memoization: Black nodes provide cached answers, preventing re-exploration

The result: each node and each edge is processed exactly once, giving O(V + E) time.

Let's trace with graph = [[1,2],[2,3],[5],[0],[5],[],[]].

Color states: White = 0 (unvisited), Gray = 1 (processing), Black = 2 (safe).

Step 1: Initialize all nodes as white. Begin checking node 0.

• Colors: [W, W, W, W, W, W, W]

Step 2: DFS(0). Mark 0 gray. Explore first neighbor: 1.

• Colors: [G, W, W, W, W, W, W]. Recursion stack: [0]

Step 3: DFS(1). Mark 1 gray. Explore first neighbor: 2.

• Colors: [G, G, W, W, W, W, W]. Stack: [0, 1]

Step 4: DFS(2). Mark 2 gray. Explore only neighbor: 5.

• Colors: [G, G, G, W, W, W, W]. Stack: [0, 1, 2]

Step 5: DFS(5). Mark 5 gray. Node 5 has NO neighbors (terminal). Mark 5 black (safe). Return true.

• Colors: [G, G, G, W, W, B, W]. Stack: [0, 1, 2]

Step 6: Back at node 2. Its only neighbor (5) returned true. All paths from 2 are safe. Mark 2 black. Return true.

• Colors: [G, G, B, W, W, B, W]. Stack: [0, 1]

Step 7: Back at node 1. Neighbor 2 was safe. Now explore next neighbor: 3. DFS(3). Mark 3 gray.

• Colors: [G, G, B, G, W, B, W]. Stack: [0, 1, 3]

Step 8: DFS(3) explores neighbor 0. Node 0 is GRAY — it is on the current recursion stack! Cycle detected: 0→1→3→0. Return false.

• Colors: [G, G, B, G, W, B, W]. Cycle: 0→1→3→0

Step 9: Cascade failure. Node 3 returns false (unsafe, stays gray). Node 1 returns false (has unsafe neighbor 3, stays gray). Node 0 returns false (stays gray).

• Colors: [G, G, B, G, W, B, W]. Nodes 0, 1, 3 are gray = unsafe.

Step 10: Move to next white node: 4. DFS(4). Mark 4 gray. Explore neighbor 5.

• Colors: [G, G, B, G, G, B, W]. Stack: [4]

Step 11: Node 5 is already BLACK (safe). Return true immediately — no need to re-explore! Mark 4 black.

• Colors: [G, G, B, G, B, B, W]. Node 4 is safe.

Step 12: Move to next white node: 6. DFS(6). Terminal (no neighbors). Mark 6 black.

• Colors: [G, G, B, G, B, B, B]. Node 6 is safe.

Step 13: All nodes processed. Collect black nodes (safe): [2, 4, 5, 6]. Gray nodes (unsafe): [0, 1, 3].

• Result: [2, 4, 5, 6]

1. Create a color array of size n, initialized to 0 (white = unvisited)
2. For each node i from 0 to n-1:
   a. Call dfs(i, color)
   b. If it returns true, add i to result
3. In dfs(node, color):
   a. If color[node] is not 0 (already processed):
   • Return color[node] == 2 (true if black/safe, false if gray/unsafe)
     b. Mark color[node] = 1 (gray — processing)
     c. For each neighbor of node:
   • If dfs(neighbor, color) returns false → return false
     d. Mark color[node] = 2 (black — safe)
     e. Return true
4. Return the result list

Time Complexity: O(V + E)

Each node is processed exactly once by the DFS. Once colored gray or black, subsequent calls to dfs(node) return immediately in O(1). For each node, we iterate through its adjacency list (its outgoing edges). Since we visit each node once and each edge once, the total time is O(V + E).

Compared to the brute force's O(V × (V + E)), this is a dramatic improvement. For V = 10^4 and E = 4 × 10^4, we go from ~5 × 10^8 to ~5 × 10^4 operations.

Space Complexity: O(V)

The color array uses O(V) space. The recursion stack in the worst case (a linear chain of nodes) can be O(V) deep. No additional data structures are needed.

Instead of asking "can this node reach a cycle?" (which requires exploring forward), let us flip the question: start from nodes we KNOW are safe, and propagate safety backward.

Who is definitely safe? Terminal nodes — they have no outgoing edges, so they trivially cannot reach a cycle.

Now think: if a node's every outgoing edge leads to a safe node, then that node itself must be safe. This gives us a propagation rule:

A node becomes safe when ALL of its outgoing edges have been "resolved" (lead to confirmed safe nodes).

This is exactly the logic of topological sort using Kahn's algorithm, but applied in a novel way:

1. Build a reverse graph: If the original has edge A→B, the reverse graph has B→A. This lets us efficiently find which nodes point TO a given node.

2. Track out-degrees: For each node, count its outgoing edges in the original graph. This represents how many of its neighbors still need to be confirmed safe.

3. Start BFS from terminal nodes (out-degree = 0). They are trivially safe.

4. Propagate safety: When we confirm a node is safe, use the reverse graph to find all nodes that point TO it. Decrease their out-degree by 1 (one more neighbor confirmed safe). When a node's out-degree reaches 0, ALL of its neighbors are confirmed safe, so it becomes safe too — add it to the queue.

5. Cycle nodes are naturally filtered: Nodes in a cycle will always have remaining out-degree > 0, because their cycle edges can never be resolved. They are never added to the queue.

This approach is iterative (no recursion), intuitive (propagate from known-safe nodes), and handles cycles automatically without explicit detection.

Let's trace with graph = [[1,2],[2,3],[5],[0],[5],[],[]].

Step 1: Compute out-degrees and build reverse graph.

• Out-degrees: [2, 2, 1, 1, 1, 0, 0]
• Reverse graph: rg[0]=[3], rg[1]=[0], rg[2]=[0,1], rg[3]=[1], rg[4]=[], rg[5]=[2,4], rg[6]=[]

Step 2: Initialize queue with terminal nodes (out-degree 0): queue = [5, 6]. Mark them safe.

Step 3: Dequeue node 5. Look at reverse graph: rg[5] = [2, 4]. Nodes 2 and 4 point to 5 in the original graph.

Step 4: Decrement out-degree[2]: 1 → 0. Node 2's only outgoing edge (to 5) is now confirmed safe. ALL paths from 2 lead to safe nodes → node 2 is safe! Enqueue 2.

Step 5: Decrement out-degree[4]: 1 → 0. Same reasoning — node 4 is safe. Enqueue 4.

• Queue: [6, 2, 4]

Step 6: Dequeue node 6. rg[6] = []. No node points to 6 in the original graph. Nothing to process.

• Queue: [2, 4]

Step 7: Dequeue node 2. rg[2] = [0, 1]. Nodes 0 and 1 point to 2.

Step 8: Decrement out-degree[0]: 2 → 1. Node 0 still has 1 unresolved outgoing edge (to node 1, which is NOT yet safe). Cannot mark 0 safe.

Step 9: Decrement out-degree[1]: 2 → 1. Node 1 still has 1 unresolved edge (to node 3, NOT yet safe). Cannot mark 1 safe.

• Queue: [4]

Step 10: Dequeue node 4. rg[4] = []. Nothing to process.

• Queue: [] (empty)

Step 11: BFS complete. Check final out-degrees: [1, 1, 0, 1, 0, 0, 0]. Nodes with out-degree 0: {2, 4, 5, 6}.

• Nodes 0, 1, 3 have remaining out-degree > 0 because they form cycle 0→1→3→0. Their mutual dependencies can never be resolved — each waits for the others to become safe, creating a deadlock.

Result: [2, 4, 5, 6]

1. Build reverse graph and compute out-degrees:
   • For each edge i → j in the original graph, add j → i to the reverse graph
   • Set outDegree[i] = graph[i].length for each node
2. Initialize BFS with terminal nodes:
   • Enqueue all nodes where outDegree[i] == 0
3. Process BFS:
   • While queue is not empty:
     a. Dequeue a safe node u
     b. For each predecessor v of u in the reverse graph:
     • Decrement outDegree[v] by 1
     • If outDegree[v] == 0, enqueue v (all its edges now lead to safe nodes)
4. Collect results:
   • Return all nodes where outDegree[i] == 0, in sorted order

Time Complexity: O(V + E)

• Building the reverse graph: iterate through all V nodes and all E edges → O(V + E)
• Computing out-degrees: O(V)
• BFS initialization (finding terminal nodes): O(V)
• BFS processing: each node is dequeued at most once, and each reverse edge is traversed at most once → O(V + E)
• Collecting results: O(V)
• Total: O(V + E)

Space Complexity: O(V + E)

• Reverse graph stores all E edges (in reversed direction): O(E)
• Out-degree array: O(V)
• BFS queue: at most V nodes → O(V)
• Result list: O(V)
• Total: O(V + E)

Comparison of all three approaches:

The BFS approach uses slightly more space (O(V + E) vs O(V)) due to the reverse graph, but eliminates recursion entirely, making it more robust for large inputs and cleaner in its reasoning about safety propagation.