当前位置: 首页 > news >正文

AcWing848有向图的拓扑排序

拓扑排序的流程:

  1. 插入(a,b),表示a->b的关系,调用add(a,b),每次吧b的入度+1,d[b]++;
    然后调用topsort,返回1表示存在拓扑序列,返回0表示不存在拓扑序列。
  2. 判断是否存在拓扑排序的逻辑:
    先把所有入度为0的点入队,这些都是可能的结果。
    取出队头t,然后出队
    因为是拉链法表示的有向图,因此访问t对应的所有出边j=e【i】
    然后删除t->j的关系,把j的入度-1,d[j] --,如果-1之后发现j的入度为0,那么j依然可能是新的拓扑序列的一员,需要把j入队!
  3. 如果拓扑排序完了之后,把所有的点都曾入队过,那么存在拓扑序列。
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100086
using namespace std;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[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(){cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<m;++i){int a,b;cin>>a>>b;add(a,b);d[b]++;}if(!topsort())puts("-1");else{for(int i=0;i<n;i++)cout<<q[i]<<' ';puts("");}return 0;
}
http://www.lryc.cn/news/428587.html

相关文章:

  • 猫咪掉毛很严重,家中猫毛该如何清理?快来看资深铲屎官经验分享
  • Midjourney进阶-反推与优化提示词(案例实操)
  • 大公报发表欧科云链署名文章:发行港元稳定币,建Web3.0新生态
  • Mybatis的一些常用知识点(面试)
  • stm32—ADC
  • 【微信小程序】吐槽生态之云开发服务端能力不足
  • AnimateDiff论文解读
  • C/C++控制台贪吃蛇游戏的实现
  • Linux 升级安装 Weblogic-补丁!
  • 苍鹰来啦!快来看呀!NGO-BiTCN-BiGRU-Attention北方苍鹰算法优化多重双向深度学习回归预测
  • 关于WebSocket必知必会的知识点
  • Go 1.19.4 Sort排序进阶-Day 12
  • python-求距离(赛氪OJ)
  • 《第二十一章 传感器与定位 - 传感器应用》
  • Windows系统命令
  • C语言函数递归
  • 【python数据分析11】——Pandas统计分析(分组聚合进行组内计算)
  • 高性能web服务器
  • 微服务案例搭建
  • SAP负库存
  • 集团数字化转型方案(三)
  • ESP32智能设备:蓝牙音箱、AI语音助手、环境监测与调节以及智能控制,基于BLE与MQTT技术(代码详解)
  • web渗透测试 学习导图
  • WordPress禁止后台自定义功能
  • (六)Flink 窗口计算
  • SQL 布尔盲注 (injection 第六关)
  • OpenAI 重回巅峰:ChatGPT-4O 最新模型超越谷歌 Gemini 1.5,多项测试夺冠!
  • 软件工程(2)面向对象方法:Booch方法与开发实例
  • 高阶面试-concurrentHashMap的整理
  • VSCode系列 - 如何用VSCode搭建C++高效开发环境(1)