LeetCode802. 找到最终的安全状态（DFS+记忆化搜索）_leetcode 记忆化搜索的题目

本题大意就是找出所有不与环连通的结点。不安全状态有两种情况：1、这个点在一个环中。2、这个点顺着边递推，会走到一个环里。所以本题的思路是给点设置三种状态，初始时的0表示未访问过的点；1表示这个点是不安全的，即这个点连接着一个环或就在环中；2表示这个点是安全的，不与任何环连通。然后对每个点进行深度优先搜索，若遇到了不安全的点，那么这个点也是不安全的，置为2。若遇到了安全的点，则表示已经有了一条可以通向终点的路径，那么这个点也是安全的，置为2。代码如下：

class Solution {
public:
    int vis[10005];
    bool dfs(vector<vector<int>>& graph,int v){
        if(vis[v]) //如果已经访问，直接返回，有记忆化搜索的意思
            return vis[v]==2;
        vis[v]=1; //先设置为1，后面的for循环为当前节点的安全性判断
        for(int i=0;i<graph[v].size();i++){
            if(!dfs(graph,graph[v][i]))
                return false;
        }
        vis[v]=2; //for循环里没有return，表明递归完成，是安全的
        return true;
    }
    
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int size=graph.size();
        vector<int>ans;
        for(int i=0;i<size;i++)
            if(dfs(graph,i))
                ans.push_back(i);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

参考博客：https://blog.csdn.net/Q_M_X_D_D_/article/details/84866866