题目链接：PTA-L3-003 社交集群(30 分)

题目背景

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

输入格式

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

其中 $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

解题思路

题目的大致意思就是，一个人可以有多个兴趣爱好，而拥有共同兴趣爱好的人可以组成一个圈子，你要找出一共有多少个圈子，以及圈子有多少人。看到这种需要进行元素分组管理的问题，我们考虑使用并查集去维护。

因为要统计圈子的人数，我们需要开两个数组，一个数组 $a$ 维护兴趣爱好的分组，一个数组 $nums$ 用于存放各个分组的人数。对于每个人的多个兴趣爱好 $h_i$，我们将第 $h_2...h_k$ 合并(merge)入 $h_1$ 形成一个圈子（分组），也就是将 $h_1$ 视为一个头节点，然后根据这个头节点$h_1$ 去更新圈子的人数，更新人数的时候需要去找到 $h_1$ 的祖先节点，对祖先节点的人数进行更新，即 $nums[find(h_1)]+1$;

最后统计一波人数即可，有一点细节要注意的是，最后的输出不能有空格！不然爆 0

完整代码

import java.io.*;
import java.util.*;

public class Main {

    private static int[] a;

    private static final int MAX = 1010;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        
        // nums 用于统计人数
        int[] nums = new int[MAX];

        // 初始化并查集
        a = new int[MAX];
        for (int i = 1; i < a.length; i++) {
            a[i] = i;
        }

        Set<Integer> set = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            String[] s = br.readLine().split(" ");
            int first = Integer.parseInt(s[1]);
            
            // 增加人数
            nums[find(first)]++;
            
            set.add(first);
            for (int j = 2; j < s.length; j++) {
                int h = Integer.parseInt(s[j]);
                set.add(h);
                // 将后面的全部并入第一个
                merge(h, first);
            }
        }

        // 统计集群人数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i < a.length; i++) {
            if (set.contains(i)) {
                int ii = find(i);
                if (ii == i) {
                    if (map.containsKey(i)) {
                        map.put(i, map.get(i) + nums[i]);
                    } else {
                        map.put(i, nums[i]);
                    }
                } else {
                    if (map.containsKey(ii)) {
                        map.put(ii, map.get(ii) + nums[i]);
                    } else {
                        map.put(ii, nums[i]);
                    }
                }
            }
        }
        // out
        pw.println(map.size());
        List<Integer> ans = new ArrayList<>(map.values());
        // 逆序排序
        ans.sort(Collections.reverseOrder());
        int i;
        for (i = 0; i < ans.size() - 1; i++) {
            pw.print(ans.get(i) + " ");
        }
        pw.print(ans.get(i));
        pw.flush();
    }

    private static void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            a[x] = y;
        }
    }

    private static int find(int x) {
        if (x != a[x]) {
            a[x] = find(a[x]);
        }
        return a[x];
    }

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

}