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;
}