HDOJ2094拓扑排序

<p>传送门：<a target=_blank href="http://acm.hdu.edu.cn/showproblem.php?pid=2094" target="_blank">http://acm.hdu.edu.cn/showproblem.php?pid=2094</a></p><p>
</p><p><pre name="code" class="cpp">/*
	一道形似拓扑排序的题HDOJ2094
	本质上考察的是对图论的理解
	
	冠军的产生：当且仅当某个点的入度为0，才可能为冠军！
	由此：
		此题的最佳做法不是建图，而是直接统计每个点的入度
	若只有一个节点u的入度为0，即：只可能是u为冠军
	
	最后，本题的难点归在了如何判断每个字母串（运动员名字）之前是否出现过
	用char或者string均可轻松完成
*/
//下面贴代码 

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;

#define input freopen("input.txt","r",stdin);
#define output freopen("output.txt","w",stdout);
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define MAXN 0x7fffffff

#define MAX 1000 
char ch[MAX][MAX];
char c[MAX];
int in[MAX];

int main()
{
	//input;
	int n,num,i,j,k,tot;
	while(cin>>n)
	{
		if (!n) break;
		Fill(in,0);
		tot=i=j=k=0;
		For2(i,1,n)
		{
			int flag=1;
			Sca_s(c);//第一个字符串输入只需判断之前的有无 
			For2(j,1,k)
				if (strcmp(ch[j],c)==0)
				{
					flag=0;break;
				}
			if (flag)
				k++,strcpy(ch[k],c);
			Sca_s(c);//第二个字符串 
			flag=1;
			For2(j,1,k)
				if (strcmp(ch[j],c)==0)//若之前出现过，则此点入度+1 
				{
					in[j]++;flag=0;break;
				}
			if (flag)//若之前未出现过，则先要新建一个节点，此点入度+1 
				k++,strcpy(ch[k],c),in[k]++;
		}
		For2(i,1,k)
			if (in[i]==0) tot++;
		if (tot==1)//当且仅当存在一个入度为0的节点 
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}