5.2 more is better-最大连通分量

• 此题和上一个很类似，只是我们需要在合并集合的同时将集合内的元素个数相加，想到可以再申请一个计数数组，其下标与并查集下标对应。

#include <stdio.h>
#define N 10000001 
int tree[N];
int sum[N];//求并查集的元素个数 
int findroot(int x){//递归查找祖先 
 if(tree[x]==-1) return x;
 else return findroot(tree[x]);
}
int main(){
 int n;//人数 
 while(scanf("%d",&n)!=EOF){
  for(int i=1;i<=N;i++){//总共 N个人,有n个朋友关系 
   tree[i]=-1;//初始化并查集，每一个城镇都是一个连通分量
      sum[i]=1;
  }
  for(int i=0;i<n;i++){
   int a,b;
   scanf("%d%d",&a,&b);
   a=findroot(a);
   b=findroot(b);//找到两者的父节点 
   if(a!=b) {
    tree[a]=b;//使原a父节点指向b父节点,即合并两者 
    sum[b]+=sum[a];
   } 
  } 
  int ans=1;//最小的最大值就是所有人都和对方不是朋友，此时最大的人数为1 
  for(int i=1;i<=N;i++)
   if(tree[i]==-1&&sum[i]>ans) ans=sum[i];//当此元素为父元素且值最大时  
  printf("%d\n\n",ans);
 }
 return 0;
}

4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8

• 注意n与N不要弄混：
  n指的的是N个人中有n个朋友关系
  N指的是并查集里有N个元素