HDOJ1232畅通工程

[c++]代码库

#include<stdio.h>
#include<string.h>
#define N 10000006
int a[N],b[N],m,sum;
void init();
int find(int x);
void insert(int x,int y);
int main()
{
     int x,y,i,j,max;
     while(scanf("%d",&m)!=EOF)
     {
         j=0;
         init();
         max=-1;
         for(i=0;i<m;i++)
         {
             scanf("%d%d",&x,&y);
             insert(x,y);
         }
         for(i=0;i<N;i++)
         {       
             if(max<b[i])
                max=b[i];     
         }
                printf("%d\n",max);

     }
     return 0;
}
void init()
{
    for(int j=0;j<N;j++)
        a[j]=j,b[j]=1;
    return ;
}
int find(int x)
{
    if(a[x]==x)
        return x;
    else
        a[x]=find(a[x]);
    return a[x];
}
void insert(int x,int y)
{
    int x1=find(x);
    int y1=find(y);
    if(x1!=y1)
    {
        if(b[x1]>=b[y1])
        {
            a[y1]=x1;
            b[x1]+=b[y1];
        }
        else
        {
            a[x1]=y1;
            b[y1]+=b[x1];

        }
    }
    return ;

}