PAT 1107. 社会集群
原题链接
中等
作者:
YAX_AC
,
2024-11-26 20:14:05
,
所有人可见
,
阅读 2
//clusters簇,团,束,串
//用vector记录该人有哪些爱好
//讲所有相同爱好的人合并到一块,就是每种爱好,有哪些人
//遍历一下每个爱好,所有相同爱好合并为一个集合
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1010;
int n;
vector<int> hobby[N];
int p[N],cnt[N];
int find(int x)
{
if(p[x]!=x) return p[x] = find(p[x]);
return p[x];
}
int main()
{
cin>>n;
for(int i = 0; i<n; i++)
{
int cnt;
scanf("%d:",&cnt);
while(cnt--)
{
int h;
cin>>h;
hobby[h].push_back(i);
}
}
for(int i = 0; i<n; i++) p[i] = i;
////遍历所有的爱好,讲所有相同爱好的人合并到一块(即与相同爱好下的第一个人合并)
for(int i = 1; i<=1000; i++)
for(int j = 1; j<hobby[i].size(); j++)
{
//讲相同爱好下每个人分别与相同爱好下的第一个人合并在一起
int a = hobby[i][0],b = hobby[i][j];
p[find(a)] = find(b);
}
//只要相同祖宗节点(统一集合),就人数++
//统计每个集合里面的人数
for(int i = 0; i<n; i++) cnt[find(i)]++;
sort(cnt,cnt+n,greater<int>());//降序来排序
int k = 0;//集合的数量
while(cnt[k]) k++;//非零数,集合就++
cout<<k<<endl;
cout<<cnt[0];
for(int i = 1; i<k; i++) cout<<' '<<cnt[i];
return 0;
}