拓扑排序,要让字典序最小,所以把栈改成堆。

 #include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
#define N 100001
priority_queue<int,vector<int>,greater<int> >Q;
int n,m,x,y;
int v[N],first[N],next[N],en,ru[N],tot,ans[N];
void AddEdge(const int &U,const int &V)
{
v[++en]=V;
next[en]=first[U];
first[U]=en;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
ru[y]++;
AddEdge(x,y);
}
for(int i=;i<=n;i++) if(!ru[i]) Q.push(i);
while(!Q.empty())
{
int last=tot;
ans[++tot]=Q.top(); Q.pop();
for(int i=first[ans[tot]];i;i=next[i])
{
ru[v[i]]--;
if(!ru[v[i]]) Q.push(v[i]);
}
}
if(tot!=n) puts("OMG.");
else
{
for(int i=;i<n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
return ;
}

最新文章

  1. exp导出做成批处理注意事项
  2. elasticsearch中常用的API
  3. 获得URL含有中文出现乱码解决
  4. canvas drag 实现拖拽拼图小游戏
  5. Bitmap动画
  6. HDU 3622 Bomb Game(二分+2SAT)
  7. GOCR.js – 使用 JS 识别出图片中的文本
  8. 一个Java对象到底占用多大内存?
  9. Centos系统python2.x升级python3.x
  10. C# 之【线程与进程】
  11. ioc构架demo
  12. stl——vector详解
  13. C语言结构体中字符数组的问题
  14. Hive基础(2)---(启动HiveServer2)Hive严格模式
  15. Emgu.CV(一)
  16. jackson json转对象 json转集合 对大小写支持
  17. JS:onmouseover 、onmouseout
  18. sql server存储过程,常用的格式
  19. swift 实践- 03 -- UILabel
  20. C++程序设计方法2:基本语法2

热门文章

  1. Eclipse来push,fetch,rebase代码
  2. 关于JAVA正则匹配空白字符的问题(全角空格与半角空格)
  3. 理解JWT(JSON Web Token)认证及python实践
  4. javascript学习教程
  5. jquery中lhgdialog插件(一)
  6. php多虚拟主机配置
  7. NYOJ 115 城市平乱 (最短路)
  8. LCD实验学习笔记(一):Makefile
  9. 关于gsl库出现access violation 0X00000005问题的解决方法
  10. python学习笔记 操作文件和目录