巡回赛
时间限制:1000 ms | 内存限制:65535 KB
难度:3
描述
世界拳击协会(WBA)是历史最悠久的世界性拳击组织,孕育了众多的世界冠军,尤其是重量级,几乎造就了大家耳熟能详的所有伟大的拳王。阿里、弗雷泽、福尔曼被称为“70年代重量级拳坛 三巨头”,是当之无愧的拳王,他们的得到的金腰带都刻有 WBA 字样。为庆贺世界拳击协会成立 50 周年,WBA 主席门多萨邀请 N 名拳击手进行了 M 场巡回比赛,每场比赛均可分出胜负,比赛过后组委会要对 N 名选手进行排序,对于每名拳手,必须满足该拳手所战胜过的对手全部排在其后才能对该排名满意。
现给出 M 场比赛的胜负关系,请你帮组委会决定是否能够唯一确定这样的排名,使得所有的拳击手都满意,若能唯一确定则输出最终排名。
输入
第一行给出测试数据的组数 T(0 如 “A B”则表示在某场比赛中 A 战胜了 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
#include
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; /*记录保存的点的个数*/
while(front1) /*如果入度为0的点大于1个,不存在拓扑排序。特别注意此处,不能写成incnt!=1,因为从最后一个点找,入度为0的点肯定是0,flag会变成0*/
{
flag=0;
break;
}
}
if(j