首页 > ACM题库 > HDU-杭电 > hdu 2094 产生冠军-并查集-[解题报告]C++
2013
12-29

hdu 2094 产生冠军-并查集-[解题报告]C++

产生冠军

问题描述 :

有一群人,打乒乓球比赛,两两捉对撕杀,每两个人之间最多打一场比赛。
球赛的规则如下:
如果A打败了B,B又打败了C,而A与C之间没有进行过比赛,那么就认定,A一定能打败C。
如果A打败了B,B又打败了C,而且,C又打败了A,那么A、B、C三者都不可能成为冠军。
根据这个规则,无需循环较量,或许就能确定冠军。你的任务就是面对一群比赛选手,在经过了若干场撕杀之后,确定是否已经实际上产生了冠军。

输入:

输入含有一些选手群,每群选手都以一个整数n(n<1000)开头,后跟n对选手的比赛结果,比赛结果以一对选手名字(中间隔一空格)表示,前者战胜后者。如果n为0,则表示输入结束。

输出:

输入含有一些选手群,每群选手都以一个整数n(n<1000)开头,后跟n对选手的比赛结果,比赛结果以一对选手名字(中间隔一空格)表示,前者战胜后者。如果n为0,则表示输入结束。

样例输入:

3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

样例输出:

Yes
No

这个题开始一看是并查集,后来改了很久,怎么改也改不过,只得翻大牛的代码,原来大牛们都是这样写的,左边的为胜利者,有边的为失败者,如果左边的胜利者只有一个没在右边出现过,那么这个就是产生的冠军,否则产生不了

#include<stdio.h>
#include<string.h>
int set[1005],n,f,c,num[1005];
char ch[1005][20];
int search( char str[] )
{
    for( int i = 1; i < c; ++i )
         if( !strcmp( str,ch[i] ) )
             return i;
    strcpy( ch[c],str );
    int len = strlen( str );
    ch[c][len] = 0;
    return c++;
}
int main( )
{
    while( scanf( "%d",&n ),n )
    {
           c = 1;
           f = 1;
           for( int i = 0; i <= 2*n; ++i )
                set[i] = 2;
           for( int i = 1; i <= n; ++i )
           {
                int x,y;
                char str1[20],str2[20];
                scanf( "%s%s",str1,str2 );
                x = search( str1 );
                y = search( str2 );
                set[y] = 0;//标记在右边出现过
                if( set[x] == 2 )//防止在左边出现的已经在右边出现了
                    set[x] = 1;//标记在左边出现过
            }
            int cout = 0;
            for( int i = 1; i < c; ++i )
                 if( set[i] == 1 )
                     ++cout;
            if( cout != 1 )
                f = 0;
            puts( f ? "Yes":"No" );
           }
    return 0;
}

解题转自:http://www.cnblogs.com/Lvsi/archive/2011/05/13/2045333.html


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。