HDU2094：产生冠军(模拟)
Problem Description有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。
Input输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。
Output对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。
Sample Input
3Alice BobSmith JohnAlice Smith5a cc dd eb ea d0
YesNo
按照我的思想是找到只在前面出现，而没有在后面出现的人只有一个，就能找出胜利者
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;struct node{ char win[100],lose[100];} a[1005];struct kode//保存所有参赛选手的名字{ char name[100]; int flag1,flag2;} s[1005];int cmp(node x,node y){ if(strcmp(x.win,y.win)!=0) return strcmp(x.win,y.win)<0; return strcmp(x.lose,y.lose)<0;}int cmp2(kode x,kode y){ return (x.name,y.name)<0;}int main(){ int n,i,j,len; while(~scanf("%d",&n),n) { len = 0; int flag1,flag2; memset(s,'\0',sizeof(s)); for(i = 0; i<n; i++) { scanf("%s%s",a[i].win,a[i].lose); flag1 = flag2 = 0; for(j = 0; j<len; j++) { if(strcmp(a[i].win,s[j].name)==0) flag1 = 1; if(strcmp(a[i].lose,s[j].name)==0) flag2 = 1; if(flag1 && flag2) break; } if(j>=len || len==0)//保存参赛选手名字 { if(!flag2) strcpy(s[len++].name,a[i].lose); if(!flag1) strcpy(s[len++].name,a[i].win); } } sort(s,s+len,cmp2); sort(a,a+n,cmp); for(i = 0; i<len; i++) s[i].flag1 = s[i].flag2 = 0; for(i = 0; i<n; i++) { int k1 = 0,k2 = 0; for(j = 0; j<len; j++) { if(strcmp(a[i].lose,s[j].name)==0)//在失败方出现过 { k1 = 1; s[j].flag2 = 1; } else if(strcmp(a[i].win,s[j].name)==0)//在省里方出现过 { k2 = 1; s[j].flag1 = 1; } if(k1 && k2) break; } } int k = 0,cnt = 0; for(i = 0; i<len; i++)//找出在胜利方出现过但没在失败方出现过的选手的数量 { if(s[i].flag1 && !s[i].flag2) cnt++; } if(cnt!=1) printf("No\n"); else printf("Yes\n"); } return 0;}