题目

https://leetcode.com/problems/find-eventual-safe-states/

题解

用 circle 表示所有环上节点和所有能到达环的节点。

DFS，实际上每一次遍历都是像遍历链表一样，判断链表是否有环，如果有环，则将整个链放进 circle 中。

有个剪枝优化：如果 DFS 过程中，遇到了 circle 中的元素，则说明之前走过的路径也应该被放进 circle 中。

最后，返回所有不在 ciecle 中的元素即可。

class Solution {
    int N;

    public List<Integer> eventualSafeNodes(int[][] graph) {
        N = graph.length;
        Set<Integer> circle = new HashSet<>();
        Set<Integer> unCircle = new HashSet<>();

        for (int i = 0; i < N; i++) {
            HashSet<Integer> seen = new HashSet<>();
            seen.add(i);
            dfs(graph, circle, unCircle, seen, i);
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            if (!circle.contains(i)) result.add(i);
        }
        return result;
    }

    public void dfs(int[][] graph, Set<Integer> circle, Set<Integer> unCircle, Set<Integer> seen, int i) {
        if (circle.contains(i)) {
            circle.addAll(seen);
            return;
        }
        if (unCircle.contains(i)) {
            return;
        }

        for (int j : graph[i]) {
            if (seen.contains(j)) {
                circle.addAll(seen);
                return;
            } else {
                seen.add(j);
                dfs(graph, circle, unCircle, seen, j);
                seen.remove(j);
            }
        }
        
        if (!circle.contains(i)) unCircle.addAll(seen);
    }
}