巡回賽

時間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：3 描述

世界拳擊協(xié)會(WBA)是歷史最悠久的世界性拳擊組織,孕育了眾多的世界冠軍,尤其是重量級,幾乎造就了大家耳熟能詳?shù)乃袀ゴ蟮娜酢０⒗铩⒏ダ诐伞⒏柭环Q為“70年代重量級拳壇 三巨頭”,是當之無愧的拳王,他們的得到的金腰帶都刻有 WBA 字樣。為慶賀世界拳擊協(xié)會成立 50 周年,WBA 主席門多薩邀請 N 名拳擊手進行了 M 場巡回比賽,每場比賽均可分出勝負,比賽過后組委會要對 N 名選手進行排序,對于每名拳手,必須滿足該拳手所戰(zhàn)勝過的對手全部排在其后才能對該排名滿意。
現(xiàn)給出 M 場比賽的勝負關(guān)系,請你幫組委會決定是否能夠唯一確定這樣的排名,使得所有的拳擊手都滿意,若能唯一確定則輸出最終排名。 輸入

第一行給出測試數(shù)據(jù)的組數(shù) T(0<T<30),對于每組測試數(shù)據(jù),首先依次給出N(1<=N<=26),M(0<=M<=1000)分別表示拳手數(shù)和比賽數(shù),拳手的姓名依次為從 A開始的前 N 個大寫字母,接下 M 行給出每場比賽的比賽結(jié)果,每行由兩個大寫字母組成,兩者之間有一空格。
如 “A B”則表示在某場比賽中 A 戰(zhàn)勝了 B。

輸出

對于每組測試,若不存在唯一的排名序列則單行輸出“No Answer”,若存在則按排名從高至低輸出拳手的名字。

樣例輸入

3 4 4 A B A C B C C D 4 4 A B A C B D C D 3 3 A B B A A C

樣例輸出

ABCD No Answer No Answer

解題思路：先找到一個入度為0的點，從這個點開始找下一個入度為0的點，直到把所有的點都找完；在找的過程中，如果同時有多個或0個入度為0的點（最后一個點除外），則不存在拓撲排序。

#include<stdio.h> #include<string.h> int map[30][30],b[50],n,m,in[50]; char c[100]; void toposort() {int incnt=0,flag=1,front=1,rear=1,i,j,k;for(i=1;i<=n;i++)if(!in[i]){incnt++;b[rear++]=i; /*找第一個入度為0的點*/}if(incnt!=1)flag=0;j=0; /*記錄保存的點的個數(shù)*/while(front<rear){incnt=0;k=b[front++];c[j++]=k+'A'-1; /*保存排好序的點*/for(i=1;i<=n;i++) /*注意是n個點，不要寫成m*/{if(map[k][i]){in[i]--;if(!in[i]) {incnt++;b[rear++]=i;/*如果入度為0，加入隊尾*/}} }if(incnt>1) /*如果入度為0的點大于1個，不存在拓撲排序。特別注意此處，不能寫成incnt!=1,因為從最后一個點找，入度為0的點肯定是0，flag會變成0*/{flag=0;break;}}if(j<n||!flag)printf("No Answer\n");else{for(i=0;i<j;i++)printf("%c",c[i]);printf("\n");} } int main() {int t,i;scanf("%d",&t);while(t--){char A,B;int a,b;memset(map,0,sizeof(map));memset(in,0,sizeof(in));memset(c,0,sizeof(c));scanf("%d%d",&n,&m);getchar();for(i=1;i<=m;i++){scanf("%c %c",&A,&B);a=A-'A'+1;b=B-'A'+1;map[a][b]=1;in[b]++;getchar();}toposort();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ 496 巡回赛 拓扑排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。