设为首页 加入收藏

TOP

NYOJ 496 巡回赛 拓扑排序
2014-11-23 21:54:22 来源: 作者: 【 】 浏览:15
Tags:NYOJ 496 巡回赛 拓扑 排序

巡回赛
时间限制: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 
 

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇C语言--测试电脑存储模式(大端存.. 下一篇hdu1284钱币问题

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·Redis压力测试实战 - (2025-12-27 09:20:24)
·高并发一上来,微服 (2025-12-27 09:20:21)
·Redis 高可用架构深 (2025-12-27 09:20:18)
·Linux 系统监控 的完 (2025-12-27 08:52:29)
·一口气总结,25 个 L (2025-12-27 08:52:27)