leetcode802-找到最终的安全状态_code:802

题目的特点就是dfs，一旦发现这条路径上有的点重复出现了，那么这条路径就被干掉。因此需要一个set来存储已经遍历过的路径。
一直对于dfs中这种set存储问题搞不明白，就比如说什么时候删除？怎么样才不会导致其中存储的数据能够代表当前路径的数，不会混乱？
下面是杰哥帮我修正的一版代码，基本思路是正确的，面对较大数组时会超时，那么就需要用Map来进行存储记忆了。也就是记录某个点是否为安全点，这样再遍历到当前点的时候可以直接判断。（map中需要存储三种状态，能，否，没遇到过）。

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> res = new ArrayList<>();
        for(int i=0;i<graph.length;i++){
            if(dfs(graph,new HashSet<>(),i)){
                res.add(i);
            }
        }
        return res;
    }
    public boolean dfs(int[][] graph, HashSet<Integer> set, int pos){
        if(set.contains(pos)){
            return false;
        }
        if(graph[pos].length==0) return true;
        set.add(pos);
        for(int j : graph[pos]){
            if(!dfs(graph, set, j)){
                set.remove(pos);
                return false;
            };
        }
        set.remove(pos);
        return true;
    }
}```
其实就是判断数组中的所有节点中哪个是满足条件的，需要从每个节点向下探索。因此开头有了个for循环，直接用if语句进行判断，ok的话就把这个节点添加进去。
如果当前节点已经存在于set中，就返回false
如果不存在，同时该节点对应位置的的数组长度为0，也就是为终点，那么就返回true
以上两个都不符合的话，就把它添加进去，然后遍历他的孩子们，判断他的孩子们是否为安全节点，那么此处就开始dfs了。一旦有一个孩子返回的为false，那么此节点的的路就不符合要求，那么就要返回false，在这之前也要在set中remove掉。
如果遍历完都ok的话，那么就要返回true，在这之前也是要在set中remove掉。
无论是返回false还是true都是要remove的。用意就是已经判断完当前点，接下来要判断同级别的其他节点了，那么当前节点是不能存在的，必须要remove，否则就会引起数据的混乱。
关于map的使用，日后再添加。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33