LeetCode 802. 找到最终的安全状态_找到最终安全状态

难度：中等。
标签：深度优先搜索，广度优先搜索，图，拓扑结构。

用深搜来做，用isSafeNodes来存储节点是否安全，1表示安全，0表示不安全，-1表示没有确定。
若一个节点是不安全的，则它对应的visited数组里的所有节点都是不安全的，反之，若一个节点遍历到了不安全的节点，则其肯定也是不安全的。
遍历过程中还要注意循环连接的部分，若遍历到的该节点已经访问过，且其安全状态没有确定，则说明循环访问了，直接判定该节点是不安全的。

正确解法：

class Solution {


    bool dfs(int now, vector<int>& visited, vector<int>& isSafeNodes, vector<vector<int>>& graph){
        if(isSafeNodes[now] == 1){
            return true;
        }
        else if(isSafeNodes[now] == 0){
            return false;
        }
        int isSafe = 1;
        for(int i = 0; i < graph[now].size(); ++i){
            int next = graph[now][i];
            if(visited[next] == 0){
                visited[next] = 1;
                if(!dfs(next, visited, isSafeNodes, graph)){
                    visited.pop_back();
                    isSafe = 0;
                    break;
                }
                visited[next] = 0;
            }
            else{
                isSafe = 0;
                break;
            }
        }
        if(isSafe){
            isSafeNodes[now] = 1;
            return true;
        }
        isSafeNodes[now] = 0;
        return false;
    }

public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        if(n <= 1){
            return {};
        }
        vector<int> isSafeNodes(n, -1);
        vector<int> ans;
        for(int i = 0; i < n; ++i){
            vector<int> visited(n);
            visited[i] = 1;
            if(dfs(i, visited, isSafeNodes, graph)){
                ans.emplace_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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

结果：

看题解，再思考后，可以优化。
visited节点可以去掉，将isSafeNodes添加一个状态来替代，当isSafeNodes[i]取值为2时，说明i在当前now的已经遍历的路径上，若下一个节点的isSafeNodes值为2，直接将当前节点标记为not safe。

class Solution {


    bool dfs(int now, vector<int>& isSafeNodes, vector<vector<int>>& graph){
        if(isSafeNodes[now] == 1){
            return true;
        }
        else if(isSafeNodes[now] == 0){
            return false;
        }
        isSafeNodes[now] = 2;
        int isSafe = 1;
        for(int i = 0; i < graph[now].size(); ++i){
            int next = graph[now][i];
            if(isSafeNodes[next] == 2){
                isSafe = 0;
                break;
            }
            if(!dfs(next, isSafeNodes, graph)){
                isSafe = 0;
                break;
            }
        }
        if(isSafe){
            isSafeNodes[now] = 1;
            return true;
        }
        isSafeNodes[now] = 0;
        return false;
    }

public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        if(n <= 1){
            return {};
        }
        vector<int> isSafeNodes(n, -1);
        vector<int> ans;
        for(int i = 0; i < n; ++i){
            if(dfs(i, isSafeNodes, graph)){
                ans.emplace_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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

结果：