图论应用——拓扑排序

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

图论应用——拓扑排序,acWing好题题解,图论

拓扑排序的原理和宽度优先搜索差不多文章来源地址https://www.toymoban.com/news/detail-858467.html

#include <iostream>
#include <cstring>
#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++)
        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];
            if(--d[j]==0)
            {
                q[++tt]=j;
            }
        }
    }
    return tt==n-1;
}

int main(void)
{
    scanf("%d%d", &n,&m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        d[b]++;
    }
    if(topsort())
    {
        for(int i=0;i<n;i++)
            printf("%d ",q[i]);
    }
    else puts("-1");
    return 0;
}

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

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

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

相关文章

  • 【C++算法模板】图论-拓扑排序,超详细注释带例题

    推荐视频链接:D01 拓扑排序 给定一张 有向无环图 ,排出所有顶点的一个序列 A A A 满足:对于图中的每条有向边 ( x , y ) (x,y) ( x , y ) , x x x 在 A A A 中都出现在 y y y 之前,则称 A A A 是该图的顶点的一个拓扑序 拓扑排序 可以判断有向图中是否有环,可以生成拓扑序列 对于下

    2024年04月15日
    浏览(41)
  • ⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用

    目录  一、原理 1. 引例:207.课程表  2. 应用场景 3. 代码思路 二、代码模板 三、练习 1、210.课程表Ⅱ🟢 2、2392.给定条件下构造举证🟡 3、310.最小高度树🟡 4、 2603.收集树中金币 🔴 1. 引例:207.课程表 就如大学课程安排一样,如果要学习数据结构与算法、机器学习这类课程

    2024年02月11日
    浏览(49)
  • 【LeetCode 热题 100】图论 专题(bfs,拓扑排序,Trie树 字典树)

    from: https://leetcode.cn/studyplan/top-100-liked/ bfs 具有 边权为1 的最短路性质 拓扑排序,入度 Trie树, 高效存储 字符串【见鬼,不知道为什么写错,需要掌握熟练度】 dfs 写法,比较简洁 bfs 写法,有最短路性质 bfs 具有 边权为1 的最短路性质 拓扑排序 模板题 数组写法,简洁,需

    2024年02月13日
    浏览(52)
  • 【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:算法百炼成神 本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面

    2024年02月03日
    浏览(46)
  • 搜索与图论(一)(深搜,广搜,树与图的存储遍历,拓扑排序)

    往深里搜,搜到叶子结点那里,回溯,到可以继续到叶子结点深搜的位置。 1、回溯一定要恢复现场 2、定义一个与当前递归层数有关的终止条件(题目要求的东西) 3、每层都用循环判断是否存在可以dfs的路 输出数字组合 全排列的思想解决n皇后问题,用三个bool数组描述限制

    2024年02月19日
    浏览(50)
  • acwing算法提高之图论--最小生成树的扩展应用

    本专题用来记录使用最小生成树算法(prim或kruskal)解决的扩展题目。 题目1 :1146新的开始 C++代码如下, 题目2 :1145北极通讯网络 C++代码如下, 题目3 :346走廊泼水节 C++代码如下, 题目4 :1148秘密的牛奶运输 C++代码如下,

    2024年04月16日
    浏览(38)
  • acwing算法提高之图论--最小生成树的典型应用

    本专题用来记录使用prim算法或kruskal算法求解的题目。 题目1 :1140最短网络 C++代码如下, 题目2 :1141局域网 C++代码如下, 题目3 :1142繁忙的都市 C++代码如下, 题目4 :1143联络员 C++代码如下, 题目5 :1144连接格点 C++代码如下,

    2024年04月27日
    浏览(41)
  • 《图》经典题题解(拓扑排序,DFS,BFS,Floyd,Dijkstra,LCA最近公共祖先,最小生成树,最短路径)(ACM)

    目录 拓扑排序 / 家谱树 p1359租用潜艇 P1938[USACO09NOV] Job Hunt S  最短路计数 797. 所有可能的路径  200.岛屿数量 DFS BFS 695.岛屿的最大面积 DFS BFS P1119 灾后重建  P1629 邮递员送信 法一:Floyd 法二:Dijkstra P3379 【模板】最近公共祖先(LCA) 最小生成树 法一:prim算法 法二:Kruskal算

    2024年04月14日
    浏览(40)
  • 【数据结构】图的应用:最小生成树;最短路径;有向无环图描述表达式;拓扑排序;逆拓扑排序;关键路径

    目录 1、最小生成树 1.1 概念  1.2 普利姆算法(Prim) 1.3 克鲁斯卡尔算法(Kruskal)  2、最短路径 2.1 迪杰斯特拉算法(Dijkstra) 2.2 弗洛伊德算法(Floyd)  2.3 BFS算法,Dijkstra算法,Floyd算法的对比 3、有向无环图描述表达式 3.1 有向无环图定义及特点 3.2 描述表达式 4、拓扑排序

    2024年02月07日
    浏览(50)
  • acwing198反素数(题解)

    对于任何正整数 x,其约数的个数记作 g(x),例如 g(1)=1、g(6)=4�(1)=1、�(6)=4。 如果某个正整数 x满足:对于任意的小于 x 的正整数 i,都有 g(x)g(i),则称 x为反素数。 例如,整数 1,2,4,61,2,4,6 等都是反素数。 现在给定一个数 N,请求出不超过 N 的最大的反素数

    2024年02月07日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包