社会集群

https://www.acwing.com/problem/content/description/1599/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

int n;
vector<int> hobby[N];
int p[N];
int cnt[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int cnt;
        scanf("%d:", &cnt);
        while (cnt -- )
        {
            int h;
            cin >> h;
            hobby[h].push_back(i);
        }
    }

    for (int i = 0; i < n; i ++ ) p[i] = i;

    for (int i = 1; i <= 1000; i ++ )
        for (int j = 1; j < hobby[i].size(); j ++ )
        {
            int a = hobby[i][0], b = hobby[i][j];
            p[find(b)] = find(a);
        }

    for (int i = 0; i < n; i ++ ) cnt[find(i)] ++ ;

    sort(cnt, cnt + n, greater<int>());

    int k = 0;
    while (cnt[k]) k ++ ;

    cout << k << endl;
    cout << cnt[0];
    for (int i = 1; i < k; i ++ ) cout << ' ' << cnt[i];
    cout << endl;

    return 0;
}