AcWing 848. 有向图的拓扑序列

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m,a,b;
int e[N],ne[N],h[N],idx;
int d[N],top[N],cnt=1;//top是拓扑排序的序列,cnt代表top中有多少元素
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort()
{queue<int> q;int t;for(int i=1;i<=n;i++)if(d[i]==0) q.push(i);//将所有入度为0的点都加入到队列之中while(q.size()){t=q.front();//每次取出队头top[cnt]=t;//加入到拓扑排序之中cnt++;//拓扑排序中的元素加1q.pop();for(int i=h[t];i!=-1;i=ne[i])//遍历t点的出边{int j=e[i];d[j]--;//入度减少if(d[j]==0) q.push(j);//如果j的入度为0,加入到队列之中}}if(cnt<n) return 0;else return 1;
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);memset(h,-1,sizeof h);//邻接表一开始没有装入任何数据,下标就是都是从-1开始的cin>>n>>m;while(m--){cin>>a>>b;add(a,b);d[b]++;//a到b b的入度++}if(topsort()==0) cout<<"-1"<<endl;else{for(int i=1;i<=n;i++)cout<<top[i]<<" ";cout<<endl;}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/277055.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

香港理工大学主办!2024年第八届电力能源系统与应用国际会议(ICoPESA 2024)即将召开!

2024年第八届电力能源系统与应用国际会议&#xff08;ICoPESA 2024&#xff09; 2024年6月24日-26日 中国香港 ICoPESA 2024-Hong Kong (icpesa.org)https://icpesa.org/index.html 会议组织单位 会议出版及检索&#xff1a; 会议录用并注册的论文将由IEEE出版&#xff0c;…

SQL Server错误:15404

执行维护计划失败&#xff0c;提示SQL Server Error 15404 无法获取有关... 异常如下图&#xff1a; 原因&#xff1a;数据库用户名与计算机名称不一致 解决办法&#xff1a;1.重名称数据库用户名 将前缀改成计算机名 2.重启SQL Server代理

Mybatis sql 控制台格式化

package com.mysql; import org.apache.commons.lang.StringUtils; import org.apache.ibatis.logging.Log;import java.util.*;/*** Description: sql 格式化* Author: DingQiMing* Date: 2023-07-17* Version: V1.0*/ public class StdOutImpl implements Log {private stati…

【消息队列开发】 测试MessageFileManager(对硬盘中的消息操作)类

文章目录 &#x1f343;前言&#x1f384;测试流程&#x1f334;准备工作&#x1f332;测试创建队列功能&#x1f333;测试统计文件的读写&#x1f38b;测试将相应消息放入文件中&#x1f38d;测试读文件里的消息到内存&#x1f340;测试删除消息&#x1f60e;测试垃圾回收⭕总…

【设计模式】一、设计模式概述

文章目录 一、设计模式概述&#xff08;一&#xff09;设计模式是什么1. 设计模式的定义2. 设计模式的组成要素3、常用设计模式一览表 &#xff08;二&#xff09;设计模式的优点&#xff08;用途&#xff09;※ 本文小结 一、设计模式概述 &#xff08;一&#xff09;设计模式…

复杂网络——半局部中心法

一、概述 由于最近写论文需要使用复杂网络知识中的半局部中心法&#xff0c;但是截止目前来说&#xff0c;网上几乎搜索不到有关的MATLAB程序代码&#xff0c;只有一篇用Python编写的程序&#xff0c;我的电脑中没有python&#xff0c;所以我花费一些时间&#xff0c;利用matla…

基于SpringBoot+Vue交流和分享平台的设计与实现(源码+部署说明+演示视频+源码介绍)

您好&#xff0c;我是码农飞哥&#xff08;wei158556&#xff09;&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。&#x1f4aa;&#x1f3fb; 1. Python基础专栏&#xff0c;基础知识一网打尽&#xff0c;9.9元买不了吃亏&#xff0c;买不了上当。 Python从入门到精通…

Day44-sersync企业实时复制实战

Day44-sersync企业实时复制实战 1. sersync实时复制工具介绍1.1 sersync工具简介1.2 sersync特点1.3 sersync图解原理1.4 sersyncrsync实时复制方案项目实践1.4.1 图解项目方案架构及实现原理1.4.2 确保远程数据传输服务部署完成1.4.3 检查当前系统nfs01是否支持inotify实时监控…

008:安装Docker

安装Docker 如果不太熟悉Linux命令&#xff0c;不想学习Linux命令&#xff0c;可以直接看文末NAS面板章节&#xff0c;通过面板&#xff0c;像使用Window一样操作NAS。 一、安装 Docker 1.安装 Docker wget -qO- https://get.docker.com/ | sh2.启动 Docker 服务 sudo sys…

qt vs 编程 字符编码 程序从源码到编译到显示过程中存在的字符编码及隐藏的字符编码转换

理解字符编码&#xff0c;请参考&#xff1a;unicode ucs2 utf16 utf8 ansi GBK GB2312 CSDN博客 了解windows字符显示必须了解locale概念 参考&#xff1a;揭密 Windows 上的各种 locale - 知乎 汉字&#xff08;或者说多字节字符&#xff09;的存放需求&#xff0c;是计算…

K8S CNI

OCI概念 OCI&#xff0c;Open Container Initiative&#xff0c;开放容器标准&#xff0c;是一个轻量级&#xff0c;开放的治理结构&#xff08;项目&#xff09;&#xff0c;在 Linux 基金会的支持下成立&#xff0c;致力于围绕容器格式和运行时创建开放的行业标准。 OCI 项目…

AI智慧校园电子班牌云平台源码

目录 家长端 学校端 电子围栏 亲情通话 课堂答题 移动化管理模式 统一资源管理平台 模板内容智能更换 家校互联 家长端 多场景通话:上学放学联系、紧急遇险求助联系、日常亲情通话关注孩子人身安全:到校离校情况、进入危险区域预警等。 学校端 课堂秩序管理:提高教…

深入浅出:Objective-C中使用MWFeedParser下载豆瓣RSS

摘要 本文旨在介绍如何在Objective-C中使用MWFeedParser库下载豆瓣RSS内容&#xff0c;同时展示如何通过爬虫代理IP技术和多线程提高爬虫的效率和安全性。 背景 随着信息量的激增&#xff0c;爬虫技术成为了获取和处理大量网络数据的重要手段。Objective-C作为一种成熟的编程…

3D地图在BI大屏中的应用实践

前言 随着商业智能的不断发展&#xff0c;数据可视化已成为一项重要工具&#xff0c;有助于用户更好地理解数据和分析结果。其中&#xff0c;3D地图作为一种可视化工具&#xff0c;已经在BI大屏中得到了广泛地应用。 3D地图通过将地理信息与数据相结合&#xff0c;以更加直观…

工具-百度云盘服务-身份认证

目标 通过百度网盘API的方式去获取网盘中的文件&#xff0c;要实现这的第一步就是需要获取网盘的权限。资料(参考) 如果期望应用访问用户的网盘文件&#xff0c;则需要经过用户同意&#xff0c;这个流程被称为“授权”。百度网盘开放平台基于 OAuth2.0 接入授权。OAuth2.0 是…

嵌入式学习第二十七天!(TCP并发模型)

TCP并发模型&#xff1a; 1. TCP多线程模型&#xff1a; 缺点&#xff1a;创建线程会带来资源开销&#xff0c;能够实现的并发量比较有限。 2. IO模型&#xff1a; 1. 阻塞IO&#xff1a; 没有数据到来时&#xff0c;可以让任务挂起&#xff0c;节省CPU资源开销&#xff0c;提…

物理隔离条件下,如何安全高效地进行内外网文件导入导出?

内外网文件导入导出通常指的是在内部网络&#xff08;内网&#xff09;和外部网络&#xff08;外网&#xff09;之间传输文件的过程。这在企业环境中尤其常见&#xff0c;因为内部网络通常包含敏感数据&#xff0c;而外部网络&#xff08;如互联网&#xff09;则允许更广泛的访…

Apache zookeeper kafka 开启SASL安全认证

背景&#xff1a;我之前安装的kafka没有开启安全鉴权&#xff0c;在没有任何凭证的情况下都可以访问kafka。搜了一圈资料&#xff0c;发现有关于sasl、acl相关的&#xff0c;准备试试。 简介 Kafka是一个高吞吐量、分布式的发布-订阅消息系统。Kafka核心模块使用Scala语言开发…

MySql入门教程--MySQL数据库基础操作

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …

k8s的pod和svc相互访问时网络链路解析

k8s的pod和svc相互访问时网络链路解析 1. k8s环境中pod相互访问1.1. k8s中pod相互访问的整体流程1.2. k8s的相同机器的不同pod相互访问1.3. k8s的不同机器的不同pod相互访问 2. k8s访问svc2.1 nat操作2.2 流量进入到后端pod 3. 疑问和思考3.1 访问pod相互访问为什么不用做nat?…