UVA 10608 Friends 并查集

最后会有几个“朋友圈子”，求最大的朋友圈的人数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int r[30005];
int x[30010];
int init(int n)/// 初始化
{
    for(int i=1;i<=n;i++)
        r[i]=i;
}

int find_(int x) ///寻找根
{
    int n=x,t;
    while(r[x]!=x)
        x=r[x];
    while(n!=r[n]){ /// 路径压缩 路过的点全部指向根
        t=r[n];
        r[n]=x;
        n=r[n];
    }
    return x;
}

int cmp(int x,int y)
{
    return x>y;
}
int main()
{
    int n,m,i,T,a,b;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init(n);
        while(m--){
            scanf("%d%d",&a,&b);
            int aa=find_(a);
            int bb=find_(b);
            if(aa!=bb)/// 合并
                r[aa]=bb;
        }

        memset(x,0,sizeof(x));
        for(i=1;i<=n;i++)
                x[find_(i)]++;/// 哈希，在一个朋友圈里，则find_(i)相同， 累加
        int ans=0;
        for(i=1;i<=n;i++)
            if(ans<x[i]) ans=x[i]; /// 找到最大的人数
        ///sort(x+1,x+n+1,cmp);  ///或者直接排序，则a[1]即为最大的数
        printf("%d\n",ans);
    }
    return 0;
}

UVA 10608 Friends 并查集

原文：http://blog.csdn.net/u014705854/article/details/41126493