描述
2013“华为杯”南京邮电大学大学生团体歌唱大赛比赛形式为：大赛分为多轮，每一轮随机选择参赛团体进行两两PK赛。当根据多轮多场的PK赛成绩能够确定排名次序时，大赛结束。
我们将问题进行简化，从1开始按递增顺序给每一个参赛团体分配一个整数编号，每个参赛团体在比赛期间表现出的歌唱水平各不相同且稳定不变，每场PK赛成绩必定胜负。给定已记录的多场PK赛成绩，请你根据胜负关系确定大赛是否应该结束，并且能够排除记录出现错误的情形。
举一个例子，共有三个参赛团体参加大赛，如果参赛团体1在PK赛中胜参赛团体3、参赛团体2在PK赛中胜参赛团体1，则可知参赛团体2的成绩比参赛团体3的成绩排名高，也说明参赛团体2的歌唱水平一定高于参赛团体3的歌唱水平；如果参赛团体1在PK赛中胜参赛团体2、参赛团体2在PK赛中胜参赛团体3、参赛团体3在PK赛中胜参赛团体1，则出现这种情形说明存在明显的记录错误。
输入
输入包括多个测试用例。
每个测试用例包括C+1行，第1行给出参赛团体总数M、已知PK赛成绩的场次数C；接下来有C行，每一行先后给出两个参赛团体编号p和q，表示编号为p的参赛团体在PK赛中胜编号为q的参赛团体；这里1≤M≤1000，1≤C≤500000，1≤p≤M，1≤q≤M，p≠q。
最后一行为“0 0”，表示输入结束，这一行无需处理。输出
针对问题输入中的每个测试用例，输出一行字符串，具体规定如下：
l 根据已记录的PK赛成绩能够确定排名次序时，则输出字符串Competition over
l 根据已记录的PK赛成绩还不能确定排名次序时，则输出字符串Competition continue
l 根据已记录的PK赛成绩不可能确定排名次序时，则输出字符串Wrong Results
样例输入
4 3
4 3
3 2
2 1
4 3
4 3
2 3
1 4
4 3
4 3
1 4
3 1
0 0
样例输出
Competition over
Competition continue
Wrong Results
分析:
拓扑排序问题,不过加入另外的一些判断条件,
1.无法完成排序,说明有环,输出结果错误
2.完成排序,并且每次拓扑排序只能有一个入度为0的,输出比赛结束
3.完成排序,当时不满足每次排序只有一个入度为0,输出比赛继续
用邻接表存储图,数组R记录入度,并且用一个头指针为R[0],尾指针为-1的队列存储入度为0的节点,降低时间复杂度.
最终的程序如下:
#include<iostream>
using namespace std;
struct node
{
int k;
struct node *next;
node()
{
k=0;
next=NULL;
}
}*A,*p;
int *R;
int M,C;
int topsort(struct node *A)
{
bool flag=false;
struct node *p,*q;
int temp_q=-1;
int num=0;
while(R[0]!=-1)
{
temp_q=-1;
if(R[R[0]]!=-1)
{
flag=true;
}
for(int i=R[0]; i!=-1;)
{
p=A[i].next;
while(p)
{
R[p->k]--;
if(R[p->k]==0)
{
R[p->k]=temp_q;
temp_q=p->k;
}
p=p->next;
}
R[0]=R[i];
num++;
i=R[i];
}
R[0]=temp_q;
}
if(num==M)
{
if(!flag)
return 0;
else
return -1;
}
else
{
return 1;
}
}
int main()
{
int a,b;
freopen("aa.txt","r",stdin);
while(scanf("%d%d",&M,&C)!=0)
{
if(!M|!C)
break;
A=new struct node[M+1];
R=new int[M+1];
T=new int[M+1];
for(int i=0; i<=M; i++)
{
R[i]=0;
T[i]=0;
}
for(int i=0; i<C; i++)
{
scanf("%d%d",&a,&b);
p=new node;
p->k=b;
p->next=A[a].next;
A[a].next=p;
R[b]++;
}
R[0]=-1;
for(int i=1; i<=M; i++)
{
if(R[i]==0)
{
R[i]=R[0];
R[0]=i;
}
}
int result=topsort(A);
if(result==0)
printf("Competition over\n");
else if(result==-1)
printf("Competition continue\n");
else
printf("Wrong Results\n");
}
return 0;
}
acm.njupt--1983,布布扣,bubuko.com
原文：http://blog.csdn.net/ice110956/article/details/20152509