【PAT】1107. Social Clusters (30)【树的层次遍历】

本文主要是介绍【PAT】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.

翻译：当你在社交网络上注册时，你总是被要求详细说明你的爱好，以便找到一些有相同爱好的潜在朋友。社交群体是指一群有共同爱好的人。你应该找到所有的社交群体。

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤1000), 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(>0) is the number of hobbies, and h_i​​ [j] is the index of the j-th hobby, which is an integer in [1, 1000].

翻译：每个输入文件包含一组测试数据。对于每组输入数据，第一行包括一个正整数N(≤1000), 代表社交网络中的总人数。假设人们被标记为1到N。接下来N行按照以下格式给出一个人的兴趣清单：
K_​i: h_i[1] h_i[2] … h_i[K_i]
K_i(>0) 代表兴趣的数量，h_i​​ [j] 表示第j个爱好，为一个 [1, 1000]的整数。

Output Specification:

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.

翻译：对于每组输入数据，输出一行网络中的社交群体总数。在第二行，按照降序排序输出每个社交群体中的人数。数字之间必须用空格隔开，行末尾不能有多余空格。

---

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

---

解题思路

实现并查集【数据结构】简单并查集的实现，并用数组保存兴趣i第一次出现的人的编号，如果后面有人爱好相同，则将他们合并。注意输出格式，可能为[1,2,1,2,1,2,1,8]之类的，你所保存的最大编号不是最大分类数，把样例的第二行3: 2 7 10放到最后一行再测试自己的代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#define INF 99999999
#define bug puts("Hello\n")
using namespace std;
int N;
int hobby[1010];
int people[1010];
int maxcount=0; 
int ccount=1;//用于分类给编号 
int ans[1010];//对people的分类结果进行计数 
void init(){for(int i=0;i<1010;i++){people[i]=i;}
}
bool cmp(int a,int b){return a>b;
}
int find(int a){if(people[a]!=a){people[a]=find(people[a]);}return people[a];
}
void union1(int a,int b){int fa=find(a);int fb=find(b);if(fa!=fb){people[fb]=fa;}
}
int main(){scanf("%d",&N);init();int K,a;for(int i=1;i<=N;i++){scanf("%d: ",&K);for(int k=0;k<K;k++){scanf("%d",&a);if(hobby[a]==0)hobby[a]=i;else union1(hobby[a],i);}}for(int i=1;i<=N;i++){int tmp=find(i);maxcount=max(maxcount,tmp);ans[tmp]++;}sort(ans,ans+maxcount+1,cmp);for(int i=0;i<maxcount+1;i++){if(ans[i]==0){maxcount=i;break;}}printf("%d\n",maxcount);for(int i=0;i<maxcount-1;i++){printf("%d ",ans[i]);}printf("%d\n",ans[maxcount-1]);return 0;
}

这篇关于【PAT】1107. Social Clusters (30)【树的层次遍历】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---