1107 Social Clusters (30分)
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.
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤), 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?? (>) is the number of hobbies, and [ is the index of the j-th hobby, which is an integer in [1, 1000].
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.
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
3
4 3 1
题意：
有n个人，每个人喜欢k个活动，如果两个人有任意一个活动相同，就称为他们处于同一个社交网络。求这n个人一共形成了多少个社交网络。
题解：
并查集。通过vector是按兴趣爱好分类，再遍历vector将同一爱好的人合并。最后用a数组统计聚类个数及类别里的个数。
AC代码：
#include<bits/stdc++.h> using namespace std; vector<int>v[1005]; int n; int a[1005]; int p=0; int fa[1005]; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void unio(int x,int y){ int yy=find(y); int xx=find(x); if(xx!=yy){ fa[yy]=xx; } } bool cmp(int x,int y){ return x>y; } int main(){ cin>>n; for(int i=1;i<=n;i++){ fa[i]=i; char s; int m; cin>>m>>s; for(int j=1;j<=m;j++){ int x; cin>>x; v[x].push_back(i); } } memset(a,0,sizeof(a)); for(int i=1;i<=1000;i++){ if(v[i].size()>0){ int x=v[i].at(0); for(int j=1;j<v[i].size();j++){ unio(x,v[i].at(j));//相同爱好合并 } } } for(int i=1;i<=n;i++){//统计聚类个数 a[find(i)]++; } sort(a+1,a+1+1000,cmp); for(int i=1;i<=1000;i++){ if(a[i]>0){ p++; } } cout<<p<<endl; for(int i=1;i<=p;i++){ cout<<a[i]; if(i!=p) cout<<" "; } return 0; }
PAT 甲级 1107 Social Clusters (30分)（并查集）
原文：https://www.cnblogs.com/caiyishuai/p/12254339.html