2023-8-29 有向图的拓扑排序

这篇具有很好参考价值的文章主要介绍了2023-8-29 有向图的拓扑排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接:有向图的拓扑排序
2023-8-29 有向图的拓扑排序,bfs,c++文章来源地址https://www.toymoban.com/news/detail-678988.html

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;

int q[N], d[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort()
{
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i++)
    {
        // 如果入度为0,添加到队列中
        if(!d[i]) q[++tt] = i;
    }
    
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j] --;
            if(d[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1;
    
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        
        add(a, b);
        // b的入度+1
        d[b] ++;
    }
    if(topsort())
    {
        for(int i = 0; i < n; i++)
        {
            cout << q[i] << ' ';
        }
    }
    else cout << "-1" << endl;
    return 0;
}

到了这里,关于2023-8-29 有向图的拓扑排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二十一、搜索与图论——拓扑序列(有向图)

    拓扑序列定义: 若一个由图中所有点构成的序列 A满足:对于图中的每条边 (x,y),x在 A中都出现在 y之前,则称 A是该图的一个拓扑序列。 人话: 始终满足每条边的起点在终点前面,从前指向后。 注意:如果在有向图中构成一个环,则必定无法构成拓扑结构,也可以证明有向

    2024年02月04日
    浏览(54)
  • 基于邻接矩阵的有向图的广度优先遍历(BFS)和深度优先遍历(DFS)算法

    概念: 广度优先遍历算法是图的另一种基本遍历算法,其基本思想是尽最大程度辐射能够覆盖的节点,并对其进行访问。 以迷宫为例,广度优先搜索则可以想象成一组人一起朝不同的方向走迷宫,当出现新的未走过的路的时候,可以理解成一个人有分身术,继续从不同的方

    2024年02月06日
    浏览(64)
  • 2023-04-09 有向图及相关算法

    有向图的的应用场景 社交网络中的关注 互联网连接 程序模块的引用 任务调度 学习计划 食物链 论文引用 无向图是特殊的有向图,即每条边都是双向的 改进Graph和WeightedGraph类使之支持有向图 Graph类的改动 WeightedGraph类的改动 有些问题,在有向图中不存在,或者我们通常不考

    2024年02月05日
    浏览(46)
  • 有向图的强连通分量

    对于一个有向图,连通分量:对于分量中任意两点u,v,必然可以从u走到v,且从v走到u. 强连通分量:极大连通分量。 求出强连通分量后,可以通过将强连通分量缩点的方式,将有向图转化成有向无环图。 求强连通分量的方法:tarjan O(n+m),时间复杂度是线性的 1 . 采用dfs来遍历整

    2024年02月10日
    浏览(39)
  • 公开游戏、基于有向图的游戏

    目录 〇,背景 一,公开游戏、策梅洛定理 1,公开游戏 2,策梅洛定理 3,非有向图游戏的公开游戏 力扣 486. 预测赢家(区间DP) 力扣 877. 石子游戏(退化贪心) 力扣 1140. 石子游戏 II(二维DP) 力扣 1406. 石子游戏 III(数列DP) 力扣 1563. 石子游戏 V(区间DP)  力扣 1686.

    2024年02月09日
    浏览(45)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(84)
  • 真题详解(有向图)-软件设计(六十二)

    真题详解(极限编程)-软件设计(六十一) https://blog.csdn.net/ke1ying/article/details/130435971 CMM指软件成熟度模型,一般1级成熟度最低,5级成熟度最高,采用更高级的CMM模型可以提高软件质量。 初始:杂乱无章。 可重复级:建立基本的项目管理过程和跟踪费用项。 已定义(确定)

    2024年02月01日
    浏览(63)
  • 有向图的邻接表和邻接矩阵

    有向图的邻接表是一种常用的表示方法,用于表示图中各个节点之间的关系。在有向图中,每条边都有一个方向,因此邻接表中的每个节点记录了该节点指向的其他节点。 具体来说,有向图的邻接表由一个由节点和它们的邻居节点列表组成的集合构成。对于每个节点,邻接表

    2024年02月22日
    浏览(40)
  • 使用颜色检测有向图中的循环

    给定一个有向图,检查该图是否包含循环。如果给定的图形至少包含一个循环,您的函数应返回 true,否则返回 false。 例子:   输入:  n = 4, e = 6  0 - 1, 0 - 2, 1 - 2, 2 - 0, 2 - 3, 3 - 3  输出: 是  解释:    

    2024年02月03日
    浏览(45)
  • 哪些方法可以判断出一个有向图是否有环

    使用 深度优先遍历 ,若从有向图上的某个顶点u出发,在 DFS(u)结束之前出现一条从顶点v到u的边,由于v在生成树上是u的子孙,则图中必定存在包含u和v的环,因此深度优先遍历可以检测一个有向图是否有环。 拓扑排序 时,当某顶点不为任何边的头时才能加入序列,存在环时环中的

    2024年02月12日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包