1107. Social Clusters (30)

2019-11-08 02:54:31

字体：大中小

来源：转载

供稿：网友

1107. Social Clusters (30) 考察并查集

#include <vector>#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int f[1005];void Init(){ for(int i=1;i<=1000;++i) f[i]=i;}int Find(int x){ int r=x; while(r!=f[r]) r=f[r]; int i=x,j; while(i!=r) { j=f[i]; f[i]=r; i=j; } return r;}void Union(int x,int y){ int X=Find(x),Y=Find(y); if(X!=Y) f[X]=Y;}int main(){ int n,rec[1005]; Init(); cin>>n; for(int i=1;i<=n;++i) { int k,h; scanf("%d: %d",&k,&h); --k; rec[i]=h; while(k--) { int t; cin>>t; Union(t,h); } } int ans[1005]={0}; for(int i=1;i<=n;++i) ans[Find(rec[i])]++; vector<int> v; int cnt=0; for(int i=1;i<=1000;++i) if(ans[i]){cnt++;v.push_back(ans[i]);} cout<<cnt<<endl; sort(v.begin(),v.end(),greater<int>()); for(auto it=v.begin();it!=v.end();++it) it!=v.end()-1?cout<<*it<<" ":cout<<*it; return 0;}

上一篇：生成1~n的排列

下一篇：为革命保护视力 --- 给 Visual Studio 换颜色