hdu1285确定比赛名次(拓扑排序+优先队列)
2024-10-18 23:30:24
第一道拓扑排序题
每次删除入度为0的点,并输出
这题要求队名小的排前面,所以要用到重载的优先队列
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;//优先队列默认是值越大,优先级越高,这里重载了,升序排列
int mapp[][],in[];
void topo(int n)
{
for(int i=;i<=n;i++)
{
if(in[i]==)q.push(i);//如果顶点的入度为0,入队
}
int c=;
while(!q.empty())
{
int v=q.top();
q.pop();
if(c<n)
{
printf("%d ",v);
c++;
}else
{
printf("%d\n",v); }
for(int i=;i<=n;i++)//删除该顶点
{
if(!mapp[v][i])
{
continue;
}
in[i]--;//目标顶点的入度减1
if(!in[i])q.push(i); //目标顶点入度==0,就入队
}
}
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
memset(mapp,,sizeof(mapp));
memset(in,,sizeof(in)); for(int i=;i<m;i++)
{
int p1,p2;
scanf("%d %d",&p1,&p2);
if(mapp[p1][p2])continue;
else mapp[p1][p2]=;
in[p2]++;//入度
}
topo(n);
} return ;
}
最新文章
- webform开发基础
- 工作邮件loop的用法
- true_kb
- 自定义的ViewGroup中添加自定义View 造成的无法显示问题(个人)
- iOS 定位精度
- Objective-C专题,是学习iOS开发的前奏(转)
- Java socket中关闭IO流后,发生什么事?(以关闭输出流为例)
- 自动更改IP地址反爬虫封锁,支持多线程(转)
- Ext中包含了几个以get开头的方法
- winform连接oracle时Oracle.DataAccess.dll版本问题
- java集合练习
- MySQL 导入外部数据时报错:1153: Got a packet bigger than &#39;max_allowed_packet&#39; 解决方案
- webpack学习最基本的使用方式(一)
- LeetCode算法题-Island Perimeter(Java实现)
- Velocity之初印象
- [视频播放] M3U8文件格式说明
- 精通Docker的50个必备教程、工具、资源
- Java--TestNG
- MySQL的innodb_flush_log_at_trx_commit配置值的设定
- vue2.0--vue-router路由
热门文章
- python模拟老师授课下课情景
- Altium制作DC002的PCB封装和3D模型
- You may experience an access violation when you access an STL object through a pointer or reference in a different DLL or EXE
- npm使用小结
- springmvc入门之HelloWorld篇
- CF585D Lizard Era: Beginning
- virtualbox+vagrant学习-2(command cli)-20-vagrant suspend命令
- mariadb密码问题
- Kafka设计解析(十二)Kafka 如何读取offset topic内容 (__consumer_offsets)
- HDU 6318 Swaps and Inversions 思路很巧妙!!!(转换为树状数组或者归并求解逆序数)