热闹的聚会
今天是小明的生日,他邀请了许多朋友参加聚会,当然,有些朋友之间由于互不认识,因此不愿意坐在同一张桌上,但是如果A认识B,且B认识C,那么A和C就算是认识的。
为了使得聚会更加热闹,就应该尽可能少用桌子。那么,最热闹(人数最多的)的那一桌一共有多少人吗?
输入格式:
首先输入一个整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据首先输入2个整数n和m (1≤n , m≤1000)。其中n表示朋友总数,并且编号从1到n;然后输入m行数据,每行2个整数A和 B (A≠B), 表示朋友A和B相互认识。
输出格式:
对于每组测试,输出最热闹的那一桌的总人数。
输入样例:
3
5 3
1 2
2 3
4 5
5 1
2 5
10 9
7 8
1 5
1 7
1 2
1 3
1 4
2 6
2 9
9 2
输出样例:
3
2
9
代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
解题代码
#include<bits/stdc++.h>
using namespace std;
int men[1005];
int ans[1005];
int find(int x)
{
if(men[x]==x){
return men[x];
}
men[x]=find(men[x]);
return men[x];
}
void Union(int a,int b) //合并
{
a = find(a);
b = find(b);
if(a!=b){
men[b]=a;
ans[a]+=ans[b];
}
}
int main()
{
int T,n,m,a,b;
cin>>T;
while(T--){
cin>>n>>m;;
for(int i=1;i<=n;i++){
men[i]=i;
ans[i]=1;
}
for(int i=0;i<m;i++){
cin>>a>>b;
Union(a,b);
}
int maxNum = 0;
for(int i=1;i<=n;i++){
if(ans[i]>maxNum&&men[i]==i)
maxNum=ans[i];
}
cout<<maxNum<<endl;
}
}
解题思路
并查集,这里要每次合并的时候,要把一边的数量存储到新合并上的一边,一开始用指针提交pta爆段错误,离谱