1.题目给出n个学生，编号为0~n-1，并给出每个学生的兴趣，求有共同兴趣的学生团体数量，和每个团体的学生数目。
2.仔细观察测试例子，发现凡是有相同兴趣的同学，都可以归为一类，并不需要团体里所有的学生都有共同兴趣，譬如学生0有兴趣A，学生1有兴趣A、B，学生2有兴趣B，那么0和1有共同兴趣A，归为一类，而2和1有共同兴趣B，所以也把2归在1所在的类，所以这个团体有3个学生。
3.主要是考察并查集。我们把每个学生的兴趣都合并到第一个兴趣所在的集合，然后统计每个学生的第一个兴趣属于哪个集合，从而把学生归到相应的集合。
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 N (<=1000), 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:
Ki: hi[1] hi[2] … hi[Ki]
where Ki (>0) is the number of hobbies, and hi[j] is the index of the j-th hobby, which is an integer in [1, 1000].
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:
8 3: 2 7 10 1: 4 2: 5 3 1: 4 1: 3 1: 4 4: 6 8 1 5 1: 4
Sample Output:
3 4 3 1
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
bool cmp(const int&a, const int&b)
{
return a > b;
}
int find(int x, map<int, int>&r)
{
if (r[x] == 0)
{//利用题目中兴趣大于0的特点，进行初始化
r[x] = x;
return x;
}
else if (r[x] == x)
return x;//如果代表就是自己，则返回x
else
{//如果代表不是自己，就把自己的代表更改为自己的代表的代表
r[x] = find(r[x], r);
return r[x];
}
}
int main(void)
{
int total;
scanf("%d", &total);
map<int, int> r;
vector<int> student(total);
for (int i = 0; i < total; i++)
{
int sum;
scanf("%d:", &sum);
//把第一个兴趣当作代表
int firstITR;
scanf("%d", &firstITR);
r[firstITR] = find(firstITR, r);//找出代表
student[i] = r[firstITR];
for (int j = 1; j < sum; j++)
{
int tmp;
scanf("%d", &tmp);
r[find(tmp, r)] = r[firstITR];//把tmp和firstITR合并
}
}
map<int, int> interestSet;
for (int i = 0; i < student.size(); i++)
{//找出各个学生所属的兴趣集合,把这个集合的人数++
interestSet[find(student[i], r)]++;
}
vector<int> ans(0);
for (map<int, int>::iterator ite = interestSet.begin(); ite != interestSet.end(); ite++)
{//把兴趣统计放到vector中
ans.push_back(ite->second);
}
//进行排序
sort(ans.begin(), ans.end(), cmp);
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++)
{
printf("%d", ans[i]);
if (i != ans.size() – 1)
printf(" ");
}
printf("\n");
return 0;
}
[/c]