G-20. Find Eventual Safe States - DFS

1. Why Do We Need This? (Problem Statement & Status Quo)

In directed graph analysis, identifying stable nodes that do not lead to infinite loops or dead ends is crucial for task scheduling, deadlock detection, and route optimization.

• Directed Graph: Given a directed graph with $V$ vertices and $E$ edges (0-indexed).
• Terminal Node: A node with no outgoing edges (out-degree = 0). There may be incoming edges, but nothing leaves it.
• Safe Node: A node is defined as a safe node if every possible path starting from that node eventually leads to a terminal node.
• Goal: Return an array containing all the safe nodes of the graph, sorted in ascending order.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: The Maze of One-Way Streets

Imagine exploring a city with strictly one-way streets (directed edges):

• Some streets lead into dead-end plazas where traffic stops completely (Terminal Nodes).
• Other streets form traffic circles (cycles) where cars loop around forever without ever escaping.
• If you start your journey at an intersection that eventually forces you into a traffic circle, you will never reach an exit plaza. Therefore, that intersection is unsafe.
• If every possible turn you can take eventually guides you to a terminal plaza (even if you explore multiple alternate routes), that intersection is safe.

3. Naive vs. Better Approach

• Naive Approach: From every single node, run a full traversal (BFS or DFS) to check every possible path and verify if it terminates. This leads to redundant path explorations and massive time complexity ($\mathcal{O}(V \cdot (V + E))$) in dense or cyclical graphs.
• Cycle Detection + DFS Backtracking (Better Approach):
  • Observe that any node that is part of a cycle can never be a safe node.
  • Furthermore, any node that leads into a cycle can also never be a safe node.
  • By leveraging a standard Directed Cycle Detection DFS algorithm (using visited and pathVisited arrays), we can systematically evaluate paths. If a DFS traversal from a node successfully completes without encountering an active recursion-stack cycle, that node and its evaluated paths are guaranteed to be safe.

4. Step-by-Step Theoretical Walkthrough

Consider a graph containing cycles and terminal nodes:

1. Identify Terminal Nodes: Spot nodes with out-degree equal to 0 (e.g., node 5 and node 6 in the lecture example).
2. Standard DFS Traversal Across Components: Run DFS starting from node 0 up to $V-1$ to handle disconnected components.
3. Tracking State:
   • visited[node] = 1: Marks a node as globally visited across all DFS branches so we don't re-traverse checked territory.
   • pathVisited[node] = 1: Marks a node as currently active in the current recursion stack (used strictly for cycle detection). When backtracking, pathVisited[node] is reset to 0.
4. Cycle Encounter Behavior: If a DFS call hits a node where pathVisited[node] == 1, a cycle is detected. We flag that node (and propagate the failure up the recursion stack) as unsafe.
5. Safe Determination: If a DFS call finishes exploring all neighbors of a node without triggering any cycle, we mark that node as safe (check[node] = 1).

5. Visualizing the DFS Call Flow & Backtracking

6. Complete Implementation (Java Code Evolution)

Below is the production-ready Java implementation integrating cycle detection with DFS to find eventual safe states.

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

class Solution {
    
    private boolean dfsCheck(int node, List<List<Integer>> adj, int[] vis, int[] pathVis, int[] check) {
        vis[node] = 1;
        pathVis[node] = 1;
        check[node] = 0; // Initially assume unsafe until proven safe
        
        // Traverse all adjacent nodes
        for (int neighbor : adj.get(node)) {
            // When the node is not visited yet
            if (vis[neighbor] == 0) {
                if (dfsCheck(neighbor, adj, vis, pathVis, check)) {
                    return true; // Cycle detected
                }
            }
            // If the node has been previously visited, 
            // but it has to be on the same path (in the current recursion stack)
            else if (pathVis[neighbor] == 1) {
                return true; // Cycle detected
            }
        }
        
        // If no cycle was found across any path from this node
        check[node] = 1;     // Mark as safe
        pathVis[node] = 0;   // Backtrack path visited state
        return false;
    }

    public List<Integer> eventualSafeNodes(int V, List<List<Integer>> adj) {
        int[] vis = new int[V];
        int[] pathVis = new int[V];
        int[] check = new int[V]; // Stores final safe status (1 = safe, 0 = unsafe)
        
        // Run DFS for all components
        for (int i = 0; i < V; i++) {
            if (vis[i] == 0) {
                dfsCheck(i, adj, vis, pathVis, check);
            }
        }
        
        List<Integer> safeNodes = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (check[i] == 1) {
                safeNodes.add(i);
            }
        }
        
        return safeNodes;
    }
}

7. Industry Reality & Debugging Mindset

• Space Complexity Trade-offs: Using three separate arrays (vis, pathVis, and check) consumes $3 \times O(N)$ auxiliary space. While advanced optimizations can combine these into a single array using custom integer state encoding (e.g., 0 for unvisited, 1 for visiting/path-visited, 2 for safe, 3 for unsafe), keeping separate arrays maintains high code readability and maintainability, which is heavily prioritized in software engineering interviews over micro-optimizations.
• Stack Overflow Risks: Because this algorithm relies on deep recursion, graphs with millions of nodes risk hitting stack overflow limits. In production environments with extreme graph depths, iterative DFS with an explicit stack or BFS-based Kahn's topological sorting (covered in the next chapter) is preferred.

8. Summary and Key Takeaways

• Terminal Nodes: Defined as nodes with an out-degree of 0 (no outgoing edges).
• Safe Nodes: Nodes where every possible path terminates at a terminal node without entering an infinite loop.
• Cycle Exclusion: Any node that is part of a cycle, or leads into a cycle, can never be a safe node.
• Dual Tracking: Utilizing a global vis array alongside a recursion-stack pathVis array ensures accurate directed cycle detection.
• Backtracking Integrity: When returning from a branch without a cycle, pathVis is reset to 0 while check permanently records safety.
• Time Complexity: $\mathcal{O}(V + E)$ as each vertex and edge is visited once during the DFS traversal.
• Space Complexity: $\mathcal{O}(V)$ across the adjacency list, recursion stack, and tracking arrays.