PAT甲级A1107---并查集

1107 Social Clusters (30分)

分析：

有n个人，每个人有若干爱好，如果两个人有任意一个相同爱好，则他们属于同一个社交网络， 求这n个人总共形成了多少个社交网络。

C++：

#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 1010;
int father[maxn];
int isRoot[maxn];
int hobby[maxn];//记录任意一个喜欢活动h的人的编号
int n;

bool cmp(int a, int b) {
    return a > b;
}

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

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

void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        father[faA] = faB;
    }
}

int main() {
    scanf("%d", &n);
    init();
    int k, h;
    for (int i = 1; i <= n; i++) {
        scanf("%d:", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &h);
            if (hobby[h] == 0) {
                hobby[h] = i;
            }
            Union(i, findFather(hobby[h]));
        }
    }
    for (int i = 1; i <= n; i++) {
        isRoot[findFather(i)]++;
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (isRoot[i] != 0) {
            res++;
        }
    }
    printf("%d\n", res);
    sort(isRoot + 1, isRoot + n + 1, cmp);
    for (int i = 1; i <= res; i++) {
        printf("%d", isRoot[i]);
        if (i != res) {
            printf(" ");
        }
    }
    return 0;
}