PAT L3-003. 社交集群
原题链接
简单
作者:
青丝蛊
,
2021-04-22 16:17:46
,
所有人可见
,
阅读 311
#include <bits/stdc++.h>
using namespace std;
int pre[1010];
int find(int x)
{
return x == pre[x] ? x : pre[x] = find(pre[x]);
}
void Union(int x, int y)
{
x = find(x), y = find(y);
if (x != y) pre[y] = x;
}
int main()
{
int n;
cin >> n;
iota(pre, pre + n + 1, 0);
map<int, vector<int>> mp;
for (int i = 1; i <= n; i++)
{
int k;
char c;
cin >> k >> c;
while (k--)
{
int x;
cin >> x;
mp[x].push_back(i);
}
}
for (auto c : mp)
{
int x = c.second[0];
for (int i = 1; i < c.second.size(); i++)
Union(x, c.second[i]);
}
map<int, int> mpp;
for (int i = 1; i <= n; i++) mpp[find(i)]++;
vector<int> v;
for (auto c : mpp)
v.push_back(c.second);
sort(v.begin(), v.end());
cout << v.size() << endl;
for (int i = v.size() - 1; i >= 0; i--)
printf(i ? "%d " : "%d", v[i]);
return 0;
}