AcWing 1597. 社会集群
原题链接
中等
作者:
周哲宇
,
2024-10-24 23:08:00
,
所有人可见
,
阅读 3
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
vector<int> hobby[N];
int p[N], cnt[N];
int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main(){
int n, hb_num = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= n; i++){
int num;
scanf("%d:", &num);
for (int j = 0; j < num; j++){
int x;
scanf("%d", &x);
hobby[x].push_back(i);
hb_num = max(hb_num, x);
}
}
for (int i = 1; i <= hb_num; i++){
for (size_t j = 1; j < hobby[i].size(); j++){
int a = hobby[i][0], b = hobby[i][j];
if (find(a) != find(b)){
p[find(a)] = find(b);
}
}
}
for (int i = 1; i <= n; i++) cnt[find(i)]++;
sort(cnt + 1, cnt + n + 1, greater<int>());
int k = 0;
for (int i = 1; cnt[i]; i ++) k ++;
cout << k << endl;
for (int i = 1; i <= n; i++){
if (!cnt[i]) break;
cout << cnt[i] << ' ';
}
return 0;
}