#题解##UVA10608 Friends#

使用并查集算法

#include<bits/stdc++.h>
using namespace std;
int arr[30010]={0};
int fi(int x)//查找根节点
{
    if(arr[x]==x)
    {
        return x;
    }
    fi(arr[x]);
}
void hb(int x,int y)//合并
{
    x=fi(x);
    y=fi(y);
    if(x!=y) arr[x]=arr[y];
}
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int n,m;
        cin>>n>>m;
        for(int j=1;j<=n;j++)
        {
            arr[j]=j;
        }
        int a,b;
        for(int k=0;k<m;k++)//先合并
        {
            cin>>a>>b;
            hb(a,b);
        }
        for(int p=1;p<=n;p++)//优化查找
        {
            arr[p]=fi(p);
        }
        int ans[30010]={0};
        for(int l=1;l<=n;l++)//统计最大集合的人数
        {
            ans[arr[l]]++;
        }
        int ma=-1;
        for(int o=1;o<=n;o++)
        {
            ma=max(ma,ans[o]);
        }
        cout<<ma<<endl;
    }
}