802. Find Eventual Safe States

Description

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is *eventually safe *if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Illustration of graph

Note:

• graph will have length at most 10000.
• The number of edges in the graph will not exceed 32000.
• Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

Solution

DFS + HashMap, O(n + e), S(n)

class Solution {
    public List<Integer> eventualSafeNodes(int[][] edges) {
        int n = edges.length;
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            graph.put(i, new HashSet<>());
        }
        
        for (int i = 0; i < edges.length; ++i) {
            for (int j = 0; j < edges[i].length; ++j) {
                graph.get(i).add(edges[i][j]);
            }
        }
        
        List<Integer> res = new ArrayList<>();
        Map<Integer, Boolean> safeMap = new HashMap<>();
        
        for (int i = 0; i < n; ++i) {
            if (dfs(graph, i, safeMap, new HashSet<>())) {
                res.add(i);
            }
        }
        
        return res;
    }
    
    private boolean dfs(Map<Integer, Set<Integer>> graph, int curr
                        , Map<Integer, Boolean> safeMap, Set<Integer> visited) {
        if (safeMap.containsKey(curr)) {
            return safeMap.get(curr);
        }
        
        if (!visited.add(curr)) {
            return false;
        }

        for (int next : graph.get(curr)) {
            if (!dfs(graph, next, safeMap, visited)) {
                safeMap.put(curr, false);
                return false;
            }
        }
        // no need to backtracking because each node could only be accessed once
        safeMap.put(curr, true);
        return true;
    }
}