您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【C++】拓扑排序

定义:
一个有向无环图的顶点组成的序列(可遍历图所有顶点的一条单向链表),需满足两个条件:
(1)该序列中包含图的每个顶点,且只出现一次;
(2)若排序中A在B的前面,则图中不存在B到A的路径;

步骤:
(1)从图中找一个入度为0的顶点A,加到路径
(2)从图中删除顶点A和A的出边(以A为起点的有向边)
(3)重复(1)(2),知道图为空
若最终图不为空,即剩下了入度不为0的顶点,则图必然有环

例题:
https://leetcode-cn.com/problems/find-eventual-safe-states/

在有向图中,以某个节点为起始节点,从该点出发,每一步沿着图中的一条有向边行走。如果到达的节点是终点(即它没有连出的有向边),则停止。

对于一个起始节点,如果从该节点出发,无论每一步选择沿哪条有向边行走,最后必然在有限步内到达终点,则将该起始节点称作是 安全 的。

返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

该有向图有 n 个节点,按 0 到 n - 1 编号,其中 n 是 graph 的节点数。图以下述形式给出:graph[i] 是编号 j 节点的一个列表,满足 (i, j) 是图的一条有向边。

示例 1:

Illustration of graph


输入:graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]
解释:示意图如上。
示例 2:

输入:graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出:[4]
 

提示:

n == graph.length
1 <= n <= 104
0 <= graph[i].length <= n
graph[i] 按严格递增顺序排列。
图中可能包含自环。
图中边的数目在范围 [1, 4 * 104] 内。

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>> &graph) {
        int n = graph.size();
        vector<vector<int>> rg(n);
        vector<int> inDeg(n);
        for (int x = 0; x < n; ++x) {
            for (int y : graph[x]) {
                rg[y].push_back(x);
            }
            inDeg[x] = graph[x].size();
        }

        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                q.push(i);
            }
        }
        while (!q.empty()) {
            int y = q.front();
            q.pop();
            for (int x : rg[y]) {
                if (--inDeg[x] == 0) {
                    q.push(x);
                }
            }
        }

        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

 


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进