首页 > 代码库 > 【拓扑排序】【堆】CH Round #57 - Story of the OI Class 查错
【拓扑排序】【堆】CH Round #57 - Story of the OI Class 查错
拓扑排序,要让字典序最小,所以把栈改成堆。
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 using namespace std; 5 #define N 100001 6 priority_queue<int,vector<int>,greater<int> >Q; 7 int n,m,x,y; 8 int v[N],first[N],next[N],en,chu[N],ru[N],tot,ans[N]; 9 void AddEdge(const int &U,const int &V)10 {11 v[++en]=V;12 next[en]=first[U];13 first[U]=en;14 }15 int main()16 {17 scanf("%d%d",&n,&m);18 for(int i=1;i<=m;i++)19 {20 scanf("%d%d",&x,&y);21 chu[x]++; ru[y]++;22 AddEdge(x,y);23 }24 for(int i=1;i<=n;i++) if(!ru[i]) Q.push(i);25 while(!Q.empty())26 {27 int last=tot;28 ans[++tot]=Q.top(); Q.pop();29 for(int i=first[ans[tot]];i;i=next[i])30 {31 ru[v[i]]--;32 if(!ru[v[i]]) Q.push(v[i]);33 }34 }35 if(tot!=n) puts("OMG.");36 else37 {38 for(int i=1;i<n;i++)39 printf("%d ",ans[i]);40 printf("%d\n",ans[n]);41 }42 return 0;43 }
【拓扑排序】【堆】CH Round #57 - Story of the OI Class 查错
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。