nyoj-496-巡回赛--拓扑排序

本文主要是介绍nyoj-496-巡回赛--拓扑排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

世界拳击协会(WBA)是历史最悠久的世界性拳击组织,孕育了众多的世界冠军,尤其是重量级,几乎造就了大家耳熟能详的所有伟大的拳王。阿里、弗雷泽、福尔曼被称为“70年代重量级拳坛 三巨头”,是当之无愧的拳王,他们的得到的金腰带都刻有 WBA 字样。为庆贺世界拳击协会成立 50 周年,WBA 主席门多萨邀请 N 名拳击手进行了 M 场巡回比赛,每场比赛均可分出胜负,比赛过后组委会要对 N 名选手进行排序,对于每名拳手,必须满足该拳手所战胜过的对手全部排在其后才能对该排名满意。
现给出 M 场比赛的胜负关系,请你帮组委会决定是否能够唯一确定这样的排名,使得所有的拳击手都满意,若能唯一确定则输出最终排名。

输入

第一行给出测试数据的组数 T(0<T<30),对于每组测试数据,首先依次给出N(1<=N<=26),M(0<=M<=1000)分别表示拳手数和比赛数,拳手的姓名依次为从 A开始的前 N 个大写字母,接下 M 行给出每场比赛的比赛结果,每行由两个大写字母组成,两者之间有一空格。
如 “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

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
vector<int> g[30];
int indu[30],vis[30];
int str[30];
int n,m;
void toposort()
{int p,flag=0;int k;for(int i=1;i<=n;i++){p=0;for(int j=1;j<=n;j++)//按照顺序查找入度为0的点{if(indu[j]==0&&!vis[j]){p++;k=j;str[i]=j;vis[k]=1;}}if(p!=1){flag=1;break;}//只有一个入度为0才满足条件，否则不行；for(int r=0;r<g[k].size();r++)  indu[g[k][r]]--;//跟此点有关系的入度减1}if(flag) printf("No Answer\n");else{for(int i=1;i<=n;i++){printf("%c",str[i]+'A'-1);}printf("\n");}
}
int main()
{int T;cin>>T;char u,v;while(T--){cin>>n>>m;memset(indu,0,sizeof(indu));memset(vis,0,sizeof(vis));memset(str,0,sizeof(str));memset(g,0,sizeof(g));for(int i=0;i<m;i++){cin>>u>>v;int x=u-'A'+1,y=v-'A'+1;g[x].push_back(y);indu[y]++;}toposort();}
}

如果你找的是唯一确定的名次，只需每次查找入度有且只有一个为0的点，然后此点打败后一点减1；

如果找的是任意符合要求的顺序，不唯一，按顺序找入度为0的点；找到之后存入数组；

这篇关于nyoj-496-巡回赛--拓扑排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---