PAT A1107 Social Clusters (30分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
/*
题意：社交簇，有共同爱好的人在一个团体（A和B有共同爱好，B和C有共同爱好，则ABC都在同一个团体），
给出n个人各自有哪些爱好，总共有多少个团体，并且按照团体中的人数降序排序 
思路：一眼看过去应该是并查集，仔细一看题目给的是每个人的爱好，本题使用
并查集应该是要以人的编号为元素的，因此需要做爱好与人编号的映射，故设置
数组hobby，用hobby[i]=j表示用户j的爱好是i。这样findFather(hobby[i])就表示是j
的father。 
*/
const int N=1e3+10;
int father[N],hobby[N],cluster[N];//cluster[i]表示以i为父节点的社交簇中有多少人 
int findFather(int x){//带路径压缩 
	if(father[x]!=x)father[x]=findFather(father[x]);
	return father[x];
}
//合并 
void Union(int a,int b){
	int fa=findFather(a);
	int fb=findFather(b);
	if(fa!=fb){
		father[fa]=fb;		
	}
} 
bool cmp(int a,int b){//降序排序 
	return a>b;
} 
int main(){
	int n;
	cin>>n;
	//初始化 
	for(int i=1;i<=n;i++){
		father[i]=i;
		cluster[i]=0;
	} 
	for(int i=1,k;i<=n;i++){
		scanf("%d: ",&k);
		for(int j=0,ki;j<k;j++){
			scanf("%d",&ki);
			if(hobby[ki]==0){//ki爱好首次出现，记录该用户i 
				hobby[ki]=i; 
			}
			//若后面再次出现ki，那么将本用户i和第一次出现ki时表示的用户hobby[ki]，这两个用户合并 
			Union(i,findFather(hobby[ki])); 
		}
	} 
	for(int i=1;i<=n;i++){
		//注意此处需要写成cluster[findFather[i]]
		//不能写成cluster[father[i]]，否则会有测试点通不过 
		cluster[findFather(i)]++;//记录每个团体的人数 
	}
	int cnt=0;//团体的个数 
	for(int i=1;i<=n;i++){
		if(cluster[i]!=0){
			cnt++; 
		}
	}
	cout<<cnt<<endl;
	sort(cluster+1,cluster+1+n,cmp);
	for(int i=1;i<=cnt;i++){
		if(i!=1)printf(" ");
		printf("%d",cluster[i]);
	}
	return 0;
}