PAT甲级——A1107 Social Clusters

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A social cluster is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer

where

Output Specification:

For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

Sample Output:

3
4 3 1

 1 #include <iostream>
 2 #include <numeric>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 int hobby[1005], father[1005];
 7 int findFather(int x) 
 8 {//查找父亲结点并进行路径压缩
 9     if (x == father[x])
10         return x;
11     int temp = findFather(father[x]);
12     father[x] = temp;
13     return temp;
14 }
15 void unionSet(int a, int b) 
16 {//合并两个集合
17     int ua = findFather(a), ub = findFather(b);
18     if (ua != ub)
19         father[ua] = ub;//这里是关键，即将此位置的father改为最近有共同爱好的人
20 }
21 int main() {
22     int n, m, a;
23     cin >> n;
24     for (int i = 0; i <= n; ++i)father[i] = i;//初始化
25     for (int i = 1; i <= n; ++i) 
26     {
27         scanf("%d:", &m);
28         while (m--) 
29         {
30             cin >> a;
31             if (hobby[a] == 0)//没有人有当前这个爱好
32                 hobby[a] = i;//i作为第一个有该爱好的人
33             else//有人喜欢该爱好
34                 unionSet(hobby[a], i);//将有同样爱好的两个人合并为一个集合
35         }
36     }
37     vector<int>result(n + 1, 0);//储存每个集合的人数
38     for (int i = 1; i < n + 1; ++i)
39         ++result[findFather(i)];//向前寻找father
40     sort(result.begin(), result.end(), [](int a, int b) {return a > b; });
41     int cnt = 0;
42     for (auto t : result)
43         if (t != 0)
44             cnt++;
45     cout << cnt << endl;
46     for (int i = 0; i < cnt; ++i)//输出result前cnt个元素(result已经从大到小排序，输出的都是集合个数不为0的)
47         printf("%s%d", i > 0 ? " " : "", result[i]);
48     return 0;
49 }