首页 > 代码库 > 【拓扑排序】【堆】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 查错