體育記者C++（前向星）
題目描述
小A是一個體育報社的記者，接受到一個艱難的任務：有N支足球隊參加足球比賽，現(xiàn)在給你一些比賽的結果，需要你給出各支球隊的排名，從1到N。
以下是給你的一些信息：
(1)沒有平局；
(2)不同的球隊排名不能相同；
(3)對于所有滿足l≤a<b≤n，第a名的球隊一定可以打敗第b名的球隊。
給你部分比賽結果，要求給出排名，并且判斷是否存在另一種排名方法滿足給你的比賽結果
輸入
第一行輸入N(1≤N≤5000)，表示球隊的數(shù)量，編號為l到N。第二行輸入M(1≤M≤100,000)，表示給出的比賽場數(shù)。接下來M行，每行兩個整數(shù)X_i，Y_i，表示X_i能打敗Y_i。
輸出
輸出包含N+1行，前N行描述球隊的排名，第i個數(shù)表示第i名的球隊（有多種排名時，輸出字典序小的），第N+1行包含一個整數(shù)，如果為0表示不存在其他的排名方法，如果為1表示還有其他的排名方法。
樣例輸入?復制
3
2
2 ?1
2 ?3
樣例輸出?復制
2
1
3
1
提示
【數(shù)據(jù)范圍】
30％的數(shù)據(jù)滿足：l≤N≤7，1≤M≤15
60％的數(shù)據(jù)滿足：l≤N≤100，1≤M≤2000
100％的數(shù)據(jù)滿足：l≤N≤5000，1≤M≤100000
程序
#include <bits/stdc++.h>using namespace std;const int maxn=100005;int m,n,a,b,c,p,cnt,head[maxn],rd[maxn],ans[maxn];bool k;priority_queue<int>q;struct edge{????int to,next;}e[500002];void bu(int x,int y){????e[++cnt].next=head[x];????e[cnt].to=y;????head[x]=cnt;????rd[y]++;}?
int main(){????k=false;????cin>>n>>m;????for(int i=1;i<=m;i++)????{????????cin>>a>>b;????????bu(a,b);????}????p=0;????for(int i=1;i<=n;i++)????????if(rd[i]==0)????????{????????????q.push(-i);????????????p++;????????}????if(p>1)????????k=1;????while(!q.empty())????{????????c=-q.top();????????ans[++ans[0]]=c;????????q.pop();????????p=0;????????for(int i=head[c];i;i=e[i].next)????????{????????????rd[e[i].to]--;????????????if(rd[e[i].to]==0)????????????{????????????????q.push(-e[i].to);????????????????p++;????????????}????????}????????if(p>1)????????????k=1;????}????for(int i=1;i<=ans[0];i++)????????cout<<ans[i]<<"\n";????cout<<k;????return 0;}標簽：
