【拓扑排序】【堆】CH Round #57 - Story of the OI Class 查错
2024-08-28 22:34:05
拓扑排序,要让字典序最小,所以把栈改成堆。
#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 ;
}
最新文章
- exp导出做成批处理注意事项
- elasticsearch中常用的API
- 获得URL含有中文出现乱码解决
- canvas drag 实现拖拽拼图小游戏
- Bitmap动画
- HDU 3622 Bomb Game(二分+2SAT)
- GOCR.js – 使用 JS 识别出图片中的文本
- 一个Java对象到底占用多大内存?
- Centos系统python2.x升级python3.x
- C# 之【线程与进程】
- ioc构架demo
- stl——vector详解
- C语言结构体中字符数组的问题
- Hive基础(2)---(启动HiveServer2)Hive严格模式
- Emgu.CV(一)
- jackson json转对象 json转集合 对大小写支持
- JS:onmouseover 、onmouseout
- sql server存储过程,常用的格式
- swift 实践- 03 -- UILabel
- C++程序设计方法2:基本语法2