[拓扑排序]leetcode802：找到最终的安全状态(medium)

题目：

题目：

思路：拓扑排序

• 难点：在于如何理解题目？题目意思是说一个节点无法进行环，则这个节点是安全的，因此使用拓扑排序从入度为 0 的点出发，将与其相连的边的顶点度进行减少，最终所有顶点中度为 0 的点即为不在环中点。

代码如下：

class Solution {
public:
    // 从所有的终端节点出发进行拓扑排序，因此终端节点相连的点也是安全节点
    // 一个节点无法进行环，则这个节点是安全的，因此使用拓扑排序从入度为 0 的点出发，将与其相连的边的顶点度进行减少，最终所有顶点中度为 0 的点即为不在环中点。
    vector<int> eventualSafeNodes(vector<vector<int>>& g) {
        int n=g.size();
        // 反向建图
        vector<vector<int>> rg(n);  // 邻接表
        vector<int> indegrees(n,0); // 入度数组
        for(int i=0;i<n;++i){
            // 反向边：j->i
            for(int j:g[i])rg[j].push_back(i);
            // 反向图顶点 i 的入度为 g[i] 的大小，因为 g[i] 中的所有反向边指向顶点 i
            indegrees[i]=g[i].size();
        }
        queue<int> q;
        // 入度为 0 的顶点入队
        for(int i=0;i<n;++i)
            if(!indegrees[i])q.push(i);
        // 开始进行 bfs
        while(q.size())
        {
            auto j=q.front();q.pop();
            // 删除所有的反向边 j->i
            for(int i:rg[j])
                if(--indegrees[i]==0)q.push(i);
        }
        vector<int> res;
        for(int i=0;i<n;++i)
            if(!indegrees[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