PAT甲级1107 Social Clusters (30 分)：[C++题解]并查集，爱好、人数

本文主要是介绍PAT甲级1107 Social Clusters (30 分)：[C++题解]并查集，爱好、人数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 题目分析
- 题目链接

题目分析

在这里插入图片描述

来源：acwing

分析: 凭爱好，分人群。注意点：爱好可传递。什么意思？意思是A和B的有共同爱好1， B和C有共同爱好2，那么认为A和C也是同一群人。

按照爱好将人分成几组。使用vector<int> hobby[N];二维数组：<爱好，人>
在这里插入图片描述

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N =1010;
int p[N];
vector<int> hobby[N]; //二维数组：<爱好，人>
int n;
int cnt[N]; //统计集合人数，不同根结点代表不同的集合int find(int x){if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main(){cin >> n;for(int i =0; i<n; i++){int cnt;scanf("%d:",&cnt);while(cnt--){int h;cin >> h;hobby[h].push_back(i); }}for(int i =0; i<n; i++) p[i] =i;//相同爱好的人合并在一起//实现爱好的传递性。喜欢1的是一群人，其中有B，B还喜欢2，喜欢2的又是一群人，通过B，就把这两群人合并在一起了。for(int i =1; i<= 1000 ;i++){for(int j = 1; j< hobby[i].size(); j++){int a= hobby[i][0], b= hobby[i][j];p[find(b)] = find(a);}}//遍历每个人，每个人都有根结点，相同根结点的是同一个集合。//统计每个集合里面的人数for(int i =0; i<n; i++) cnt[find(i)] ++;sort(cnt,cnt+n, greater<int>());//求集合个数int k = 0;while(cnt[k]) k++;cout<< k<<endl;//输出集合的人数cout<<cnt[0];for(int i =1; i<k; i++) cout<<" "<<cnt[i];}