LeetCode 802 找到最终的安全状态_802. 找到最终的安全状态 c语言

题目描述：
在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。

现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。

哪些节点最终是安全的？ 结果返回一个有序的数组。

该有向图有 N 个节点，标签为 0, 1, …, N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表，满足 (i, j) 是图的一条有向边。

思路：
逆向图：
1、记录原来每个节点的出度
2、求逆向图
3、设置一个队列，记录安全节点；设置一个哈希表，记录安全节点
4、首先把原来出度为0的节点存入队列
5、再把与队列中节点相连的节点，（加以判断）存入队列
6、最后遍历所有队列中的节点
7、通过哈希表找到所有的安全节点

代码如下：

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int N=graph.size();
        vector<int>degree(N,0);
        vector<int>res;
        vector<vector<int>>rev(N,vector<int>(0));
        for(int i=0;i<N;i++){
            degree[i]=graph[i].size();
            for(int j=0;j<graph[i].size();j++){
                rev[graph[i][j]].push_back(i);
            }
        }
        vector<bool>myhash(N,0);
        queue<int>q;
        for(int i=0;i<N;i++){
            if(degree[i]==0){
                q.push(i);
                myhash[i]=1;
            }
        }
        while(q.size()){
            int i=q.front();
            q.pop();
            for(auto j:rev[i]){
                degree[j]--;
                if(degree[j]==0){
                    q.push(j);
                    myhash[j]=1;
                }
            }
        }
        for(int i=0;i<N;i++){
            if(myhash[i])
            res.push_back(i);
        }
        return res;
    }
};
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