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.
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:
K?i??: h?i??[1] h?i??[2] ... h?i??[K?i??]
where K?i?? (>) is the number of hobbies, and [ is the index of the j-th hobby, which is an integer in [1, 1000].
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.
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
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 }
原文：https://www.cnblogs.com/zzw1024/p/11442303.html