1107. Social Clusters (30) 并查集

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
int father[1001];
int hobby[1001];
int gnum[1001];

int find(int x){
    while (x != father[x]) {
        x = father[x];
    }
    return x;
}

void Union(int a, int b){
    a = find(a);
    b = find(b);
    if(a < b) father[b] = a;
    else father[a] = b;
}

void init(){
    for (int i = 0; i < 1001; i++) {
        father[i] = i;
    }
}

int main(){
    init();
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d:", &k);
        for (int j = 0; j < k; j++) {
            int t;
            scanf("%d", &t);
            if(!hobby[t])
                hobby[t] = i;
            Union(i, find(hobby[t]));
        }
    }
    for (int i = 1; i <= n; i++) {
        gnum[find(i)]++;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if(gnum[i] != 0) cnt++;
    }
    sort(gnum, gnum + 1001);
    cout << cnt << endl;
    for (int i = 1000; i > 1000 - cnt; i--) {
        printf("%d%c", gnum[i], i == 1000-cnt+1 ? '\n' : ' ');
    }
    
    return 0;
}