802. Find Eventual Safe States

Problem Description

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

Examples:

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation: Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

Constraints:

• n == graph.length
• 1 ≤ n ≤ 10^4
• 0 ≤ graph[i].length ≤ n
• 0 ≤ graph[i][j] ≤ n - 1
• graph[i] is sorted in ascending order
• graph[i] does not contain duplicates

Python Solution

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        safe = {}
        
        def dfs(i, visited):
            if i in visited:
                return i in safe
            if i in safe:
                return safe[i]
                
            visited.add(i)
            safe[i] = True
            
            for nei in graph[i]:
                if not dfs(nei, visited):
                    safe[i] = False
                    break
                    
            return safe[i]
        
        return [i for i in range(n) if dfs(i, set())]

Implementation Notes:

• Uses DFS with cycle detection to find safe nodes
• A node is safe if all its paths lead to terminal nodes
• Time complexity: O(V + E) where V is number of vertices and E is number of edges
• Space complexity: O(V)

Java Solution

class Solution {
    private boolean[] safe;
    private boolean[] visited;
    private boolean[] inStack;
    
    public List eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        safe = new boolean[n];
        visited = new boolean[n];
        inStack = new boolean[n];
        List result = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (dfs(i, graph)) {
                result.add(i);
            }
        }
        
        return result;
    }
    
    private boolean dfs(int node, int[][] graph) {
        if (inStack[node]) return false;
        if (visited[node]) return safe[node];
        
        visited[node] = true;
        inStack[node] = true;
        
        for (int next : graph[node]) {
            if (!dfs(next, graph)) {
                return false;
            }
        }
        
        inStack[node] = false;
        safe[node] = true;
        return true;
    }
}

C++ Solution

class Solution {
public:
    vector eventualSafeNodes(vector>& graph) {
        int n = graph.size();
        vector safe(n, false);
        vector visited(n, false);
        vector inStack(n, false);
        vector result;
        
        for (int i = 0; i < n; i++) {
            if (dfs(i, graph, safe, visited, inStack)) {
                result.push_back(i);
            }
        }
        
        return result;
    }
    
private:
    bool dfs(int node, vector>& graph, vector& safe,
             vector& visited, vector& inStack) {
        if (inStack[node]) return false;
        if (visited[node]) return safe[node];
        
        visited[node] = true;
        inStack[node] = true;
        
        for (int next : graph[node]) {
            if (!dfs(next, graph, safe, visited, inStack)) {
                return false;
            }
        }
        
        inStack[node] = false;
        safe[node] = true;
        return true;
    }
};

JavaScript Solution

function eventualSafeNodes(graph) {
    const n = graph.length;
    const safe = new Array(n).fill(false);
    const visited = new Array(n).fill(false);
    const inStack = new Array(n).fill(false);
    const result = [];
    
    function dfs(node) {
        if (inStack[node]) return false;
        if (visited[node]) return safe[node];
        
        visited[node] = true;
        inStack[node] = true;
        
        for (const next of graph[node]) {
            if (!dfs(next)) {
                return false;
            }
        }
        
        inStack[node] = false;
        safe[node] = true;
        return true;
    }
    
    for (let i = 0; i < n; i++) {
        if (dfs(i)) {
            result.push(i);
        }
    }
    
    return result;
}

C# Solution

public class Solution {
    private bool[] safe;
    private bool[] visited;
    private bool[] inStack;
    
    public IList EventualSafeNodes(int[][] graph) {
        int n = graph.Length;
        safe = new bool[n];
        visited = new bool[n];
        inStack = new bool[n];
        var result = new List();
        
        for (int i = 0; i < n; i++) {
            if (DFS(i, graph)) {
                result.Add(i);
            }
        }
        
        return result;
    }
    
    private bool DFS(int node, int[][] graph) {
        if (inStack[node]) return false;
        if (visited[node]) return safe[node];
        
        visited[node] = true;
        inStack[node] = true;
        
        foreach (int next in graph[node]) {
            if (!DFS(next, graph)) {
                return false;
            }
        }
        
        inStack[node] = false;
        safe[node] = true;
        return true;
    }
}

Implementation Notes:

• Uses DFS with cycle detection
• Maintains three arrays: safe, visited, and inStack for tracking node states
• Time complexity: O(V + E)
• Space complexity: O(V)