链接：PAT Advanced1107
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:
K?i?? : h?i?? [1] h?i?? [2] … h?i?? [K?i?? ]
where K?i?? (>0) is the number of hobbies, and h?i?? [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
题意：
有N个人，每个人喜欢若干项活动，如果两个人有任意一个活动相同，那么称他们处于同一个社交网络（若A和B属于同一个社交网络，B和C属于同一个社交网络，那么A、B、C同属于一个社交网络）。求这N个人总共形成了多少个社交网络，并以非递增顺序输出各个社交网络的人数。
分析：
每个社交网络相当于一个集合，若A、B有任意一个活动相同，则将两个集合合并，最后遍历每个人，找出一共有多少个不同的根节点（即集合数目），同时记录各集合内的元素数量。
以下代码：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1010;
int father[maxn],cnt[maxn]={
0};
vector<int> ans,hobby[maxn]; //hobby[h]中存储喜欢的活动为h的所有人的编号
bool cmp(int a,int b){
return a>b; }
void init(int n) //不要忘了并查集的初始化
{
for(int i=1;i<=n;i++)father[i]=i;
}
int findfather(int x) //查找根结点
{
int root=x;while(root!=father[root]) //找到根结点root=father[root];//路径压缩,可将查找的时间复杂度降为 O(1)while(x!=father[x]) //重新走一遍路径{
//让路径上的所有结点直接和根结点相连int t=x;x=father[x]; //继续向上走father[t]=root; //当前结点直接与根结点相连}return root;
}
int Union(int a,int b) //合并集合
{
int Fa=findfather(a);int Fb=findfather(b);if(Fa!=Fb)father[Fa]=Fb;
}
int main()
{
int N,K,h;scanf("%d",&N);init(N);for(int i=1;i<=N;i++){
scanf("%d%*c",&K);while(K--){
scanf("%d",&h);for(int j=0;j<hobby[h].size();j++)Union(i,hobby[h][j]); //和有相同活动的人集合合并hobby[h].push_back(i);}}for(int i=1;i<=N;i++)cnt[findfather(i)]++; //cnt下标为根结点编号for(int i=1;i<=N;i++){
if(cnt[i]!=0) //找到元素个数不为0集合ans.push_back(cnt[i]); //存储元素个数}sort(ans.begin(),ans.end(),cmp); //排序printf("%d\n",ans.size()); //输出for(int i=0;i<ans.size();i++){
if(i!=0)printf(" ");printf("%d",ans[i]);}return 0;
}