HDU 2094 产生冠军 dfs加map容器

解题报告：有一群人在打乒乓球比赛，需要在这一群人里面选出一个冠军，现在规定，若a赢了b,b又赢了c那么如果a与c没有比赛的话，就默认a赢了c，而如果c赢了a的话，则这三个人里面选不出冠军，还有就是如果一个人没有输给别人，但是存在一个人跟这个人之间的输赢关系不能确定的话，也是作为选不出冠军的情况，现在输入一群人的比赛情况，要你确定，利用这组比赛情况能不能确定一个冠军，能的话输出Yes，否则输出No。

感觉这题应该有很多种不同的解法，其中由于输入的是选手的名字，所以还要用到map容器。我的做法是枚举每一个人是否有可能是冠军，即从这个人开始出发，用dfs搜索，看这个人一共赢了多少个人，然后他赢的人的个数是否是总的比赛的人数M-1,如果是，则说明他就是冠军，如果枚举每一个人都不满足的话，则说明没有冠军。要注意的是，

这样做有很多情况可以减掉，第一，如果某个人；有过输给别人的记录，则这个人可以直接跳过，不需要看他赢了多少人，这样可以减掉一大部分，然后每次已经搜过的要标记掉，即已经被人打败过的要标记掉，要不然如果两个人都同时赢了同一个人的话，则这个人将会被统计两次。代码贴上：

 #include<cstdio>

 #include<cstring>

 #include<map>

 #include<iostream>

 #include<string>

 #include<cstring>

 using namespace std;

 const int maxn = +;

 int M,num;

 bool map2[maxn][maxn],mark[maxn];

 map<string,int> mp1;

 pair<map<string,int>::iterator,bool> iter;

 int visit[maxn];

 int find(const char *s) {

     string s1 = s;

     iter = mp1.insert(pair<string,int> (s1,++M));

     if(iter.second)

     return M;

     else {

         M--;

         return mp1[s1];

     }

 }

 void dfs(int x) {

     for(int i = ;i<=M;++i)

     if(!mark[i] && map2[x][i]) {

         num++;

         mark[i] = ;

         dfs(i);

     }

 }

 int main() {

     int n;

     char str1[],str2[];

     while(scanf("%d",&n),n) {

         M = ;

         memset(map2,,sizeof(map2));

         memset(visit,,sizeof(visit));

         for(int i = ;i<=n;++i) {

             scanf("%s%s",str1,str2);

             int x = find(str1);

             int y = find(str2);

             map2[x][y] = ;

             visit[y] = ;

         }

         bool flag = ;

         for(int i = ;i<=M;++i)

         if(!visit[i]) {

             num = ;

             memset(mark,,sizeof(mark));

             mark[i] = ;

             dfs(i);

             if(num == M-) {

                 flag = ;

                 break;

             }

         }

         printf(flag? "Yes\n":"No\n");

         mp1.clear();

     }

     return ;

 }