搜索与图论-拓扑序列

news/2025/3/18 23:31:34/

为什么记录呢
因为不记录全忘了
虽然记了也不一定会看

  1. 有向无环图一定有拓扑序列
  2. 邮箱无环图 - 拓扑图
  1. 入度为0的点作为起点
  2. 入度为0的点入队列
  3. 枚举出边 t->j
  4. 删掉当前边,t->j . j的入度减1
  5. 判断j的入度是否为0,来判断是否加入队列
  1. 有环: 不存在入度为0的点
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>using namespace std;const int maxn = 100010;int h[maxn], e[maxn], ne[maxn], idx;int q[maxn],d[maxn];int n;int hh = 0, tt = -1;void add(int a, int b){e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}bool topsort(){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;// cout<<"j: "<< j << " "; }}}// cout<<"tt " << tt << "n-1 "<< n-1 << '\n';return tt == n-1;}int main(){int m,a,b;memset(h , -1, sizeof h);cin >> n >> m;for(int i = 0; i < m; i++){cin>>a>>b;add(a,b);// cout<<"b  "<< b << " ";d[b]++;}for(int i = 1; i <= n; i++){if(d[i] == 0){// cout<<"i: " << i<<'\n';q[++tt] = i;}}if(topsort()){for(int i = 0; i < n; i++){cout<<q[i] << " ";}}else cout<<-1<< '\n';return 0;
}

http://www.ppmy.cn/news/1070425.html

相关文章

视频汇聚/视频监控管理平台EasyCVR接入海康SDK协议后无法播放该如何解决?

开源EasyDarwin视频监控/安防监控/视频汇聚EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;在视频监控播放上&#xff0c;视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多路视频流&#…

大学生该怎么认清当下的就业环境呢?

大学生毕业后进入职场&#xff0c;面临的就业环境也在不断发生变化。为了更好地适应这个变化莫测的环境&#xff0c;大学生需要认清当下的就业环境&#xff0c;并做出相应的应对策略。 了解行业趋势&#xff0c;抓住就业机会 如今&#xff0c;各行各业的竞争日益激烈&#xff…

ManageEngine ServiceDesk Plus之CVE漏洞

什么是CVE&#xff1f; CVE的英文全称是“Common Vulnerabilities & Exposures”即通用漏洞披露&#xff0c;CVE像是一个字典表&#xff0c;为广泛认同的信息安全漏洞给出一个公共的名称。 使用一个公共名称&#xff0c;可以帮助用户在各自独立的各种漏洞数据库中共享数据…

day60

第十章 单调栈part03 有了之前单调栈的铺垫&#xff0c;这道题目就不难了。 84.柱状图中最大的矩形 代码随想录 今天是训练营最后一天&#xff0c;恭喜坚持两个月的录友们&#xff0c;接下来可以写一篇自己 代码随想录一刷的总结。好好回顾一下&#xff0c;这两个月自己的博客…

RAID磁盘阵列(RAID0/1/4/6/1+0)

目录 一、概述&#xff1a; 二、RAID 级别介绍 RAID 0 RAID 1 RAID 4 RAID 5 RAID 6 RAID10&#xff1a; 一、概述&#xff1a; RAID&#xff08; Redundant Array of Inexpensive Disks&#xff09;称为廉价磁盘冗余阵列。 RAID 的基本思想是把多个便宜的小磁盘组合到…

探索性测试入门指南

探索性测试是一种依靠测试人员经验的软件测试方法&#xff0c;强调测试人员可以自由地对系统进行交互和操作&#xff0c;自由地设计和执行测试&#xff0c;而不是严格遵循预定的测试用例。在探索性测试过程中&#xff0c;测试人员依靠经验和直觉来模拟用户的各种使用情形&#…

java Server Sent Event 实现消息推送

我选择的是Server-sent events)&#xff0c;简称SSE。主要是我理解起来简单。 这个链接是介绍 几种消息推送的方式java实现web实时消息推送的七种方案--个人学习记录_java实时推送前端数据_自不惘的博客-CSDN博客 一、java服务端代码 //SSE&#xff1a;一种服务器发送事件(S…

医学影像PACS系统源码,患者登记、图像采集和处理、图像存储、报告产生的影像系统

PACS系统是医院影像科室中应用的一种系统&#xff0c;主要用于获取、传输、存档和处理医学影像。它通过各种接口&#xff0c;如模拟、DICOM和网络&#xff0c;以数字化的方式将各种医学影像&#xff0c;如核磁共振、CT扫描、超声波等保存起来&#xff0c;并在需要时能够快速调取…