开发者社区云计算文章正文

1107. Social Clusters (30) 并查集

2018-02-11 871

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： #include #include #include #include using namespace std;int father[1001];int hobby[1001];int gnum[1001];...

#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;
}