PAT甲級1107-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 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個(gè)人，每一個(gè)人喜歡k個(gè)活動，如果兩個(gè)人有任意一個(gè)活動相同，則他們處于同一個(gè)社交網(wǎng)絡(luò)。典型的并查集題目
三.代碼部分
#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合并的函數(shù)
int x=findfather(a);
int y=findfather(b);
if(x!=y)
father[x]=y;
}
bool cmp(int a,int b){//自定義比較函數(shù)
return a>b;
}
int main(){
int d,e,f;
cin>>d;
iota(father,father+d+1,0);//C++中的初始化函數(shù)，每次賦值之后第三個(gè)數(shù)默認(rèn)加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]);//二者進(jìn)行合并
}
}
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函數(shù)可以計(jì)算出從第一個(gè)參數(shù)到第二個(gè)參數(shù)中等于第三個(gè)參數(shù)的值的個(gè)數(shù)
cout<<temp<<endl;
for(int i=0;i<temp;i++)
printf("%s%d",i>0?" ":"",result[i]);
return 0;
} 
