NYOJ 496 巡回賽 拓撲排序

巡回賽
時間限制：1000 ms  |  內存限制：65535 KB
難度：3
描述
世界拳擊協會(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解題思路：先找到一個入度為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; /*記錄保存的點的個數*/
	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;
}