leetcode：802. 找到最终的安全状态_802 找到最终的安全状态

题目来源

• leetcode：802. 找到最终的安全状态

题目描述

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
     
    }
};
1
2
3
4
5
6

题目解析

深度优先遍历 （官方答案）

根据题意，如果起始节点位于一个环内，或者能够到达一个环，则该节点不是安全的。否则，该节点就是安全的。

我们可以使用DFS来找环，并在深度优先搜索的时候，用三色对节点进行标记，标记的规则如下：

• 白色（用0表示）：该节点尚未被访问
• 灰色（用1表示）：该节点位于递归栈中，或者在某个环上
• 黑色（用2表示）：该节点搜索完毕，是一个安全节点

当我们首次访问一个节点时，将其标记为灰色，并继续搜索与其相连的节点。

如果在搜索过程中遇到了一个灰色节点，则说明找到了一个环，此时退出搜索，栈中的节点扔保持为灰色，这一做法可以将[找到了环]这一信息传递到栈中所有节点上

如果搜索过程中没有遇到灰色节点，则说明没有遇到环，那么递归返回前，我们将其标记由灰色改为黑色，即表示它是一个安全的节点。

class Solution {
    bool safe(vector<vector<int>>& graph, std::vector<int> &color, int x){
        if(color[x] > 0){ //该节点已经被访问过了
            return color[x] == 2;  // 判断该节点是否安全
        }
        color[x] = 1;  // 正在访问中
        for(int y : graph[x]){
            if(!safe(graph, color, y)){  // 只要有一个未被访问到
                return false;
            }
        }
        color[x] = 2;
        return true;
    }
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        std::vector<int> color(n);
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (safe(graph, color, 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
25
26
27

方向图 + 拓扑排序

分析：

• 根据题意，对于某一个节点，如果它当前在某个环内，或者有可能走到某个环上，那么它就是不安全的，因为如果遇到环，就无法在有限步内到达终点。
• 根据上面的分析，我们发现，最简单的安全点就是无路可走的终点（也即出度为 00 的节点）。而拓展到一般情况，如果一个节点所指向的点均为安全点，那么这个点也是安全点。如何提取出这些安全点呢？我们需要避开图中的环路，提到环路，我们会自然地想到拓扑排序
• 拓扑排序是找到图中入度为 0的节点，以及仅由入度为 0 节点所指向的节点。 ，而本题是找到图中**出度为 0 的节点，以及仅指向出度为 0 节点的节点。**刚好是相反的情况，所以，我们将题目给定的有向图变为反图（也即有向边的起点、终点互换），那么所有安全点便可以通过拓扑排序来求解了

思路：

• 从终点逆向推导，将指向终点的边都删除，删除后如果指向它的节点没有出边了，那么这个节点也可以作为终点继续寻找
• 这个节点其实就是逆向拓扑排序，将没有出边的节点入队，删除指向当前节点的所有边，将没有出边的节点入队
• 为结果需要严格递增排序，所以拓扑排序结束之后再统计 入度 为 0 的节点。

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        std::vector<int> degree(n);
        std::map<int, std::set<int>> map;
        // 从终端开始推导: 终点---> 起点
        for (int begin = 0; begin < graph.size(); ++begin) {
            degree[begin] = graph[begin].size();  // out
            for(auto end : graph[begin]){
                map[end].insert(begin);
            }
        }

        std::queue<int> queue;
        for (int i = 0; i < degree.size(); ++i) {
            if(degree[i] == 0){
                queue.push(i);  // out = 0
            }
        }

        std::set<int> set;
        while (!queue.empty()){
            auto top = queue.front(); queue.pop();
            set.insert(top);
            for(auto next : map[top]){
                degree[next]--;
                if(degree[next] == 0){
                    queue.push(next);
                }
            }
        }

        return {set.begin(), set.end()};
    }
};
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

深度优先遍历（我的答案）

class Solution {
    /*
    第1步：找出所有的终端节点： out == 0
    第2步：以每一个节点(g.nodes)为起点，进行BFS，判断是不是安全节点：
        安全节点： 所有可能的路径都可以到达终端节点
    
    DSF时哪些节点可能不是安全节点呢？
        - DFS发现了环，有两种情况：
            - 自环  
            - 普通环
        - 对于每一个节点的所有可能的下一条路径，只要有一条路径不是安全节点，那么就一定不是安全节点
    */
    std::map<int, bool> status;    // 是不是安全节点， 终端一定是安全节点

    // 当前节点是不是安全节点
    // i一定会有效
    bool process(std::vector<std::vector<int>> &graph, int i, std::set<int> set){
        // 当前节点已经判断过了
        if(status.count(i)){
            return status[i];
        }

        bool flag = true;
        auto load = graph[i];  // 当前节点可能的路
        for(auto l : load){
            // 自环是不是终端节点呢？ in = 1, out = 1，一定不是终端节点
            if(l == i  || set.count(l)){  // 自环路 || 形成了环
                flag = false;
                break;
            }

            set.insert(l);
            if(!process(graph, l, set)){  // 只要有一条路不能到达终点
                flag = false;
                break;
            }
            set.erase(l);
        }
        return status[i] = flag;
    }
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        // 一定要先：找出所有的终端节点
        for(int i = 0; i < graph.size(); i++){
            if(graph[i].empty()){
                status[i] = true;   //g[i] -- > [....]  , i.out = g[i].size(); 因此如果为空的话，那么一定是终端节点
            }
        }

        // 然后枚举每一个作为起点，判断能不能全部到达终点
        for(int i = 0; i < graph.size(); i++){
            std::set<int> path{i};
            process(graph, i, path);
        }

        // 获取最终的答案
        std::vector<int> vec;
        for(auto iter : status){
            if(iter.second){
                vec.push_back(iter.first);
            }
        }

        return vec;
    }
};
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
54
55
56
57
58
59
60
61
62
63
64
65
66