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

题目链接

PAT甲级1107 Social Clusters (30 分)
https://www.acwing.com/problem/content/1599/

总结

以上是生活随笔为你收集整理的PAT甲级1107 Social Clusters (30 分)：[C++题解]并查集，爱好、人数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。