HDOJ-1856-More is better: 간단합니다.max 원 찾기 속도를 최적화합니다.C 언어로 출력을 입력합니다.

3680 단어 more
#include<cstdio>
#include<algorithm>
using namespace std;
#define Size 10000000
int Par[Size+1], Sum[Size+1];

int GetPar( int a )
{
        if( Par[a]!=a )
            Par[a] = GetPar( Par[a] );
        return Par[a];
}

void Union( int a, int b )
{
        int Pa = GetPar( a );
        int Pb = GetPar( b );

        if( Pa == Pb )
            return ;
        Par[Pa] = Pb;
        Sum[Pb]+=Sum[Pa];
}

int main()
{
    int n, A, B;
        while( ~scanf("%d", &n) ){
                for( int i=1; i<=Size; i++ ){
                        Par[i] = i;
                        Sum[i]=1;
                }
                int ans=1;
                for( int i=0; i<n; i++ )
                {
                        scanf( "%d %d", &A, &B );
                        Union( A, B );
                        ans = max( Sum[Par[B]], ans );//         max one
                }
                printf( "%d
", ans ); } return 0; }

좋은 웹페이지 즐겨찾기