802. Find Eventual Safe States [Medium]

/**
 * 自己的思路，DFS
 * 开始代码一直runtime error，看了discuss发现是因为helper里没有在进入递归前将dp[i]设为false
 * Runtime: 4 ms, faster than 99.18%
 * Memory Usage: 49 MB, less than 39.07%
 */
class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> res = new ArrayList<>();
        Boolean[] visited = new Boolean[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (helper(visited, graph, i)) {
                res.add(i);
            }
        }
        return res;
    }
    
    private boolean helper(Boolean[] visited, int[][] graph, int i) {
        if (visited[i] != null)
            return visited[i];
        visited[i] = false; // 这里一定要先将visited设为false，因为在这条路的递归中可能会再回到当前节点，如果在进入递归前没给visited[i]一个值，会造成死循环，回到当前节点就说明是false了
        for (int next : graph[i]) {
            if (!helper(visited, graph, next)) {
                return false;
            }
        }
        visited[i] = true;
        return true;
    }
}

第一次复习

和上次代码一样，而且也没有想到BFS的办法

看discuss找到了一个，但是比较tricky，只当锻炼思维

思路和计划课表（