AcWing 1597. 社会集群
原题链接
中等
作者:
aゞ法簩庫巴
,
2024-04-09 18:29:11
,
所有人可见
,
阅读 3
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
int n, k, h;
int arr[N];
int parent[N];
int cnt[N];
int find(int num) {
if (num == parent[num]) return num;
return parent[num] = find(parent[num]);
}
inline void union_merge(int x, int y) { parent[find(x)] = find(y); }
int main() {
cin >> n;
for (size_t i = 1; i <= n; i++) parent[i] = i;
for (size_t i = 1; i <= n; i++) {
(cin >> k).ignore();
while (k--) {
cin >> h;
if (!arr[h]) arr[h] = i;
else union_merge(arr[h], i);
}
}
for (size_t i = 1; i <= n; i++) cnt[find(i)]++;
sort(cnt, cnt + n + 1, greater<int>());
int len = 0;
for (size_t i = 0; cnt[i]; i++) len++;
cout << len << endl;
for (size_t i = 0; cnt[i]; i++) cout << cnt[i] << " ";
}