一.题目
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个人，每一个人喜欢k个活动，如果两个人有任意一个活动相同，则他们处于同一个社交网络。典型的并查集题目
三.代码部分
#include<bits/stdc++.h>
using namespace std;
int father[10001],hobby[10001];
int findfather(int x){//findfather的模板
if(x==father[x])
return x;
return father[x]=findfather(father[x]);
}
void Union(int a,int b){//father合并的函数
int x=findfather(a);
int y=findfather(b);
if(x!=y)
father[x]=y;
}
bool cmp(int a,int b){//自定义比较函数
return a>b;
}
int main(){
int d,e,f;
cin>>d;
iota(father,father+d+1,0);//C++中的初始化函数，每次赋值之后第三个数默认加1
for(int i=1;i<=d;i++){//注意i的初值与变化
scanf("%d:",&e);
while(e--){
cin>>f;
if(hobby[f]==0)
hobby[f]=i;
else
Union(i,hobby[f]);//二者进行合并
}
}
int result[d+1]={0};
for(int i=1;i<d+1;i++)
result[findfather(i)]++;
sort(result,result+1+d,cmp);//排序之后非0元素排列到后面了
int temp=d+1-count(result,result+1+d,0);//count函数可以计算出从第一个参数到第二个参数中等于第三个参数的值的个数
cout<<temp<<endl;
for(int i=0;i<temp;i++)
printf("%s%d",i>0?" ":"",result[i]);
return 0;
} 
京公网安备 11010502036488号