AcWing 1597. 社会集群
原题链接
中等
作者:
编号002
,
2024-07-23 17:50:14
,
所有人可见
,
阅读 1
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int fa[N],n;
bool st[N][N]; //st[i][j]:i是否有爱好j
map<int,int> cnt;
vector<int> ans;
int find(int x)
{
if(fa[x]!=x)fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
fa[i]=i;
string s;
cin>>s;
int m=0;
for(int i=0;s[i]!=':';i++)
m=m*10+s[i]-'0';
while(m--)
{
int x;
cin>>x;
st[i][x]=true;
}
}
//<=1e6
for(int i=1;i<=1000;i++) //遍历爱好
{
int t=0;
for(int j=1;j<=n;j++) //遍历人
{
if(st[j][i])
{
if(!t)t=j; //经遍历到的第一个人作为根结点
fa[find(j)]=find(t);
}
}
}
for(int i=1;i<=n;i++)
cnt[find(i)]++;
cout<<cnt.size()<<endl;
for(auto t:cnt)
ans.push_back(t.second);
sort(ans.begin(),ans.end());
for(int i=ans.size()-1;i>=0;i--)
cout<<ans[i]<<' ';
return 0;
}