一、题目描述
原题链接
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.
Input Specification:
??Output Specification:
Sample Input:
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
Sample Output:
3
4 3 1
二、解题思路
并查集的题目，这道题最重要的是把题读懂，每个人有不同的爱好，有着相同爱好的人自然可以形成一个cluster，当然，拥有不同爱好的人如果有一个共同的朋友，则他们也属于同一个cluster。基于这个，我们就可以按照爱好来进行并查集的操作，能够相连的爱好，我们把它们的根设为同一个，那么我们就可以遍历所有的人，看他的第一个爱好的根结点，使cnt数组对应自增即可。建立一个set用于存放不同的爱好对应cluster的根，遍历这个set，将cnt数组对应的数存入ans中，随后从大到小排序，遍历输出即可。
三、AC代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int maxn = 1010;
int father[maxn], cnt[maxn] = {
0};
vector<vector<int> > people;
bool cmp(int a, int b) //从大到小排序
{
return a > b;
}
int findFather(int x) //找并查集的根
{
int a = x; //存放当前xwhile(x != father[x]) x = father[x]; //找到根while(a != father[a]) //将一族的根结点全部设为x{
int z = a; //存放当前aa = father[a]; //更新它的上一层father[z] = x; //将根设为x}return x;
}
void Union(int a, int b) //并操作
{
int faA =findFather(a), faB = findFather(b);father[faA] = faB;
}
int main()
{
int N, K, id, tmp;for(int i=0; i<maxn; i++) father[i] = i;scanf("%d", &N);people.resize(N);for(int i=0; i<N; i++){
scanf("%d: %d", &K, &id);people[i].push_back(id); //因为我们是对爱好进行并查集操作的，所以我们先输入一个爱好作为每个人所在cluster的标志for(int j=1; j<K; j++){
scanf("%d", &tmp);Union(id, tmp); //将两个cluster合并people[i].push_back(tmp);}}set<int> clusters;vector<int> ans;for(int i=0; i<N; i++) //遍历所有人，找出这个人所在cluster的根，并且对应的人数++{
int root = findFather(people[i][0]);clusters.insert(root);cnt[root]++;}for(set<int>::iterator it = clusters.begin(); it!=clusters.end(); it++) //遍历集合{
ans.push_back(cnt[*it]); //每个cluster的人数}sort(ans.begin(), ans.end(), cmp); //按人数从大到小排序printf("%d\n", clusters.size());for(int i=0; i<ans.size(); i++)i == 0 ? printf("%d", ans[i]) : printf(" %d", ans[i]);return 0;
}