http://acm.hdu.edu.cn/showproblem.php?pid=1856

典型的并查集

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 10000005
using namespace std;
int father[maxn];
int isRoot[maxn];
int mx;
int findFather(int x){
    if(x == father[x]) return x;
    else{
        int tp = findFather(father[x]);
        father[x] = tp;
        return tp;
    }
}
void Union(int a,int b){
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB){
        father[faA] = faB;
        isRoot[faB] += isRoot[faA];
        if(isRoot[faB] > mx) mx = isRoot[faB];
    }
}
void init( ){
    for(int i=1;i< maxn;i++){
        father[i]=i;
        isRoot[i]=1;
    }
}
int main(){
    int n,x,y;
    while(scanf("%d",&n) != EOF){   
    init();
    mx = 1;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        Union(x,y); 
    }
    printf("%d\n",mx);
      }
    return 0;
}