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

拓扑排序(优先队列)queue、C++

N个小朋友,编号 1∼N,要排成一队。在安排每个人的顺序时,有 M 个要求,每个要求包含两个整数 a,b,表示小朋友 a 要排在小朋友 b 的前面。
请你找出符合所有要求的排队顺序。

输入格式
第一行包含整数 N,M。接下来 M 行,每行包含两个整数 a,b。

输出格式
按排好队列从前到后的顺序在一行内输出每个小朋友的编号。保证至少存在一个符合条件的顺序。当符合条件的排队顺序不唯一时,编号更小的小朋友尽量更靠前。

数据范围
1≤N≤500,
1≤M≤5000,
1≤a,b≤N,
保证数对 (a,b) 各不相同。

输入样例:
4 3
1 2
2 3
4 3

输出样例:
1 2 4 3

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int>> heap;
const int N=510,M=5010;
int h[N],e[N],ne[N],idx;
int rd[N];
int n,m;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort()
{for(int i=1;i<=n;i++)if(!rd[i])heap.push(i);while(heap.size()){int k=heap.top();cout<<k<<" ";heap.pop();for(int i=h[k];i!=-1;i=ne[i]){int j=e[i];if(--rd[j]==0)heap.push(j);}}
}
int main()
{cin>>n>>m;memset(h,-1,sizeof(h));while(m--){int a,b;cin>>a>>b;add(a,b);rd[b]++;}topsort();return 0;
}

相关文章:

拓扑排序(优先队列)queue、C++

N个小朋友&#xff0c;编号 1∼N&#xff0c;要排成一队。在安排每个人的顺序时&#xff0c;有 M 个要求&#xff0c;每个要求包含两个整数 a,b&#xff0c;表示小朋友 a 要排在小朋友 b 的前面。 请你找出符合所有要求的排队顺序。 输入格式 第一行包含整数 N,M。接下来 M 行…...

【Spring】SpringBoot 统一功能处理

文章目录 前言1. 拦截器1.1 什么是拦截器1.2 拦截器的使用1.2.1 自定义拦截器1.2.2 注册配置拦截器 1.3 拦截器详解1.3.1 拦截路径1.3.2 拦截器执行流程1.3.3 适配器模式 2. 统一数据返回格式3. 统一异常处理 前言 在日常使用 Spring 框架进行开发的时候&#xff0c;对于一些板…...

拦截器HandlerInterceptor | springmvc系列

拦截器&#xff0c;通俗来来将&#xff0c;就是我们将访问某个路径的请求给拦截下来&#xff0c;然后可以对这个请求做一些操作 基本使用 创建拦截器类 让类实现HandlerInterceptor接口&#xff0c;重写接口中的三个方法。 Component //定义拦截器类&#xff0c;实现Handle…...

【SQL server】DML触发器监控数据库字段值改变

文章目录 前言DML触发器基本思路创建触发器固定字段触发示例完整示例代码变量声明查询新旧值插入数据到日志表效果视频动态字段触发示例完整代码示例触发器基本信息变量声明定义游标打开游标临时表创建循环处理字段...

Docker容器(二)安装与初体验wordpress

一、安装 1.1关闭SeLinux SeLinux&#xff08;Security-Enhanced Linux&#xff09;是一种基于Linux内核的安全模块&#xff0c;旨在提供更严格的访问控制和安全策略。它通过强制实施安全策略来限制系统资源的访问&#xff0c;从而保护系统免受恶意软件和未经授权的访问。 在…...

Odrive 学习系列二:将烧录工具从ST-Link V2修改为JLink

一、背景: 通过观察odrive解压后的内容,可以看到在下面配置文件及makefile文件中的配置设置的均为openOCD + stlink v2,例如makefile中: # This is only a stub for various commands. # Tup is used for the actual compilation.BUILD_DIR = build FIRMWARE = $(BUILD_DI…...

ffmpeg api-codec-param-test.c源码讲解

try_decode_video_frame /*** 尝试解码视频帧** param codec_ctx 解码器上下文* param pkt 待解码的视频数据包* param decode 是否解码标志&#xff0c;如果为1&#xff0c;则进行解码&#xff0c;如果为0&#xff0c;则不解码* return 返回0表示成功&#xff0c;否则表示出错…...

Hive学习(14)json解析get_json_object()函数

一、语法 目的&#xff1a;在一个标准JSON字符串中&#xff0c;按照指定方式抽取指定的字符串。 string get_json_object(string <json>, string <path>) 参数说明 json&#xff1a;必填。STRING类型。标准的JSON格式对象&#xff0c;格式为{Key:Value, Key:Val…...

sqlilabs第五十五五十六关

Less-55(GET - challenge - Union- 14 queries allowed -Variation 2) 手工注入 结束 自动注入 想到一个办法能绕过需要用到IP池就可以&#xff08;但是我没有&#xff09; Less-56(GET - challenge - Union- 14 queries allowed -Variation 3) 手工注入...

Vue2 实现带输入的动态表格,限制el-input输入位数以及输入规则(负数、小数、整数)

Vue2 实现el-input带输入限制的动态表格&#xff0c;限制输入位数以及输入规则&#xff08;负数、小数、整数&#xff09; 在这个 Vue2 项目中&#xff0c;我们实现一个限制输入位数&#xff08;整数16位&#xff0c;小数10位&#xff09;以及输入规则&#xff08;负数、小数、…...

反爬虫策略:使用FastAPI限制接口访问速率

目录 引言 一、网络爬虫的威胁 二、FastAPI 简介 三、反爬虫策略 四、具体实现 五、其他反爬虫策略 六、总结 引言 在当今的数字时代&#xff0c;数据已经成为了一种宝贵的资源。无论是商业决策、科学研究还是日常生活&#xff0c;我们都需要从大量的数据中获取有价值的…...

响应式编程初探-自定义实现Reactive Streams规范

最近在学响应式编程&#xff0c;这里先记录下&#xff0c;响应式编程的一些基础内容 1.名词解释 Reactive Streams、Reactor、WebFlux以及响应式编程之间存在密切的关系&#xff0c;它们共同构成了在Java生态系统中处理异步和响应式编程的一系列工具和框架。 Reactive Streams…...

如何使用LightPicture+cpolar搭建个人云图床随时随地公网访问

文章目录 1.前言2. Lightpicture网站搭建2.1. Lightpicture下载和安装2.2. Lightpicture网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 现在的手机越来越先进&#xff0c;功能也越来越多&#xff0c;而手机…...

华媒舍:高效率的新闻资讯新闻媒体宣发套餐内容推广计划方案

怎样让自己的新闻资讯可以被大众孰知&#xff0c;变成了每一个新闻媒体宣发者一同存在的困难。下面我们就给大家介绍一套高效率的新闻资讯新闻媒体宣发套餐内容推广计划方案&#xff0c;致力于帮助新闻媒体宣发者提升宣发高效率&#xff0c;提高新闻资讯的传播性。 1.新闻媒体宣…...

MySQL使用通配符进行数据搜索以及过滤

目录 1.什么是通配符&#xff1f; 2.通配符之→百分号(%) 3.通配符之→下划线(_) 4.通配符使用注意事项 *本文涉及概念来源于图灵程序设计丛书&#xff0c;数据库系列——《MySQL必知必会》 1.什么是通配符&#xff1f; 通配符(wildcard) &#xff1a;用来匹配值的一部分…...

Overleaf IEEE白嫖即将失效!

之前白嫖Overleaf用IEEE的&#xff0c;最长只能到一月份了&#xff01;&#xff08;官方回复&#xff09; 翻译一下&#xff1a; IEEE不支持这种Collaboratec白嫖了已经白嫖的&#xff0c;到2024年1月份过期没有白嫖的&#xff0c;已经无法获得了...

条件控制生成---相关论文集合

1. IP-Adapter 论文地址 解决问题&#xff1a; 如何将图片作为prompt输入网络&#xff0c;并无需更改开源模型参数 解决思路&#xff1a; 新增一个cross-attention layers&#xff0c;结果与text prompt的cross-attention layers结果相加后输入网络&#xff0c;只需要训练Wk, …...

揭秘亚马逊、ebay测评系统:从稳定环境搭建到防关联技术

在亚马逊、ebay平台上进行测评、lu卡和lu货、采退等活动&#xff0c;首要问题是确保环境的安全性和稳定性。一个稳定的环境是进行测评和lu卡、lu货、采退的基础&#xff0c;如果无法解决安全性问题&#xff0c;那么从事这些项目就不值得。我们在环境技术研发领域已经有l七年的经…...

街机模拟游戏逆向工程(HACKROM)教程:[3]街机的ROM与RAM

简介 在街机模拟器中运行一个街机游戏&#xff0c;我们除了需要一个模拟器工具 &#xff0c;也需要有一个街机的ROM文件。街机的ROM文件&#xff0c;称之为Read-Only Memory&#xff0c;可以理解为只读存储器。在 ROM文件中&#xff0c;包括了游戏运行所需要的指令代码&#x…...

Element UI CascaderPanel级联组件使用和踩坑总结

Element UI CascaderPanel级联组件使用和踩坑总结 问题背景 需求中需要用到Element UI的 CascaderPanel组件&#xff0c;并且支持多选&#xff0c;定制化需求&#xff0c;比如某节点被选择&#xff0c;等价于该节点下面所有子节点都被选择&#xff0c; CascaderPanel组件返回…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...