传送门

第一道拓扑排序题

每次删除入度为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 ;
}

最新文章

  1. webform开发基础
  2. 工作邮件loop的用法
  3. true_kb
  4. 自定义的ViewGroup中添加自定义View 造成的无法显示问题(个人)
  5. iOS 定位精度
  6. Objective-C专题,是学习iOS开发的前奏(转)
  7. Java socket中关闭IO流后,发生什么事?(以关闭输出流为例)
  8. 自动更改IP地址反爬虫封锁,支持多线程(转)
  9. Ext中包含了几个以get开头的方法
  10. winform连接oracle时Oracle.DataAccess.dll版本问题
  11. java集合练习
  12. MySQL 导入外部数据时报错:1153: Got a packet bigger than &#39;max_allowed_packet&#39; 解决方案
  13. webpack学习最基本的使用方式(一)
  14. LeetCode算法题-Island Perimeter(Java实现)
  15. Velocity之初印象
  16. [视频播放] M3U8文件格式说明
  17. 精通Docker的50个必备教程、工具、资源
  18. Java--TestNG
  19. MySQL的innodb_flush_log_at_trx_commit配置值的设定
  20. vue2.0--vue-router路由

热门文章

  1. python模拟老师授课下课情景
  2. Altium制作DC002的PCB封装和3D模型
  3. You may experience an access violation when you access an STL object through a pointer or reference in a different DLL or EXE
  4. npm使用小结
  5. springmvc入门之HelloWorld篇
  6. CF585D Lizard Era: Beginning
  7. virtualbox+vagrant学习-2(command cli)-20-vagrant suspend命令
  8. mariadb密码问题
  9. Kafka设计解析(十二)Kafka 如何读取offset topic内容 (__consumer_offsets)
  10. HDU 6318 Swaps and Inversions 思路很巧妙!!!(转换为树状数组或者归并求解逆序数)