PAT L3-003 社交集群

https://pintia.cn/problem-sets/994805046380707840/problems/994805053141925888

当你在社交网络平台注册时，一般总是被要求填写你的个人兴趣爱好，以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。

输入格式：

输入在第一行给出一个正整数 N（≤1000），为社交网络平台注册的所有用户的人数。于是这些人从 1 到 N 编号。随后 N 行，每行按以下格式给出一个人的兴趣爱好列表：

K​i​​: h​i​​[1] h​i​​[2] ... h​i​​[K​i​​]

其中K​i​​(>0)是兴趣爱好的个数，h​i​​[j]是第j个兴趣爱好的编号，为区间 [1, 1000] 内的整数。

输出格式：

首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔，行末不得有多余空格。

输入样例：

8

3: 2 7 10

1: 4

2: 5 3

1: 4

1: 3

1: 4

4: 6 8 1 5

1: 4

输出样例：

3

4 3 1

 

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

int N;

int f[maxn], vis[maxn];

vector<int> root;

void init() {

    for(int i = 1; i <= N; i ++)

        f[i] = i;

}

int Find(int x) {

    if(f[x] != x) f[x] = Find(f[x]);

    return f[x];

}

void Merge(int x, int y) {

    int fx = Find(x);

    int fy = Find(y);

    if(fx != fy)

        f[fy] = fx;

}

int main() {

    memset(vis, 0, sizeof(vis));

    scanf("%d", &N);

    root.resize(N + 1);

    init();

    for(int i = 1; i <= N; i ++) {

        int K;

        scanf("%d:", &K);

        while(K --) {

            int x;

            scanf("%d", &x);

            if(vis[x] == 0)

                vis[x] = i;

            Merge(i, Find(vis[x]));

        }

    }

    for(int i = 1; i <= N; i ++)

        root[Find(i)] ++;

    int cnt = 0;

    for(int i = 1; i <= N; i ++)

        if(root[i]) cnt ++;

    sort(root.rbegin(), root.rend());

    printf("%d\n", cnt);

    for(int i = 0; i < cnt; i ++)

        printf("%d%s", root[i], i != cnt - 1 ? " " : "\n");

    return 0;

}

　　并查集