Source:

PAT A1107 Social Clusters (30 分)

Description:

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 (≤), 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].

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

Keys:

Code:

 /*
time: 2019-06-23 14:07:12
problem: PAT_A1107#Social Clusters
AC: 34:25 题目大意:
把一群具有相同爱好的人归为一个社交圈,找出所有的社交圈
输入:
第一行给出,总人数N<=1e3,编号从1~N
接下来N行,给出第i个人的,爱好总数K,各个爱好
输出:
第一行给出,社交圈总数
第二行给出,各个社交圈的人数,从多到少 基本思路:
基于兴趣做并查集操作,
输入每个人的兴趣,首个兴趣的Hash值+1,标记人数
统计父结点个数及其孩子的哈希值即可
*/
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int M=1e3+;
int fa[M],man[M]={},ans[M]={}; int Father(int v)
{
int x=v,s;
while(fa[v] != v)
v = fa[v];
while(fa[x] != x){
s = fa[x];
fa[x] = v;
x = s;
}
return v;
} void Union(int v1, int v2)
{
int f1 = Father(v1);
int f2 = Father(v2);
fa[f2] = f1;
Father(v2);
} int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif // ONLINE_JUDGE for(int i=; i<M; i++)
fa[i]=i; int n,m,h1,h2;
set<int> hobby,clster;
scanf("%d", &n);
for(int i=; i<n; i++)
{
scanf("%d:%d", &m,&h1);
man[h1]++;
hobby.insert(h1);
for(int j=; j<m; j++)
{
scanf("%d", &h2);
hobby.insert(h2);
Union(h1,h2);
h1=h2;
}
}
for(auto it=hobby.begin(); it!=hobby.end(); it++){
ans[Father(*it)] += man[*it];
clster.insert(Father(*it));
}
printf("%d\n", clster.size());
sort(ans, ans+M, greater<int>() );
for(int i=; i<clster.size(); i++)
printf("%d%c", ans[i], i+==clster.size()?'\n':' '); return ;
}

最新文章

  1. 使用配置文件来配置JDBC连接数据库
  2. easyui dialog iframe
  3. 使用MiniProfiler跟踪MVC + EF + Bootstrap 2 权限管理系统的性能消耗
  4. 一个参数大小写引发的uploadify报错 &quot;Syntax error, unrecognized expression: #&quot;
  5. python leetcode 日记--Maximal Square--221
  6. IIS网站服务器性能优化指南(转载)
  7. 【转】kylin优化
  8. jquery一些方法
  9. 嵌入dll到rtf文件
  10. Unity Shader Prpperties
  11. 【HDOJ】3505 Writing Robot
  12. (原)python中import caffe提示no module named google.protobuf.internal
  13. 启动及重新启动nginx,重启nginx后丢失nginx.pid问题解决
  14. ARPU_百度百科
  15. js获取当前日期,网页头部用
  16. Hibernate 异常 集锦
  17. 页面设计-数据列表 DataGrid
  18. git push 时提示用户名或密码相关错误信息
  19. delphi做的程序如何连接SQL数据库
  20. (84)Wangdao.com第十八天_JavaScript Promise 对象

热门文章

  1. [vs执行报错] CRT detected that the application wrote to memory after end of heap buffer
  2. 3.1 The Interpolating Polynomial(站点)
  3. ADT 压缩包 R23.0.0
  4. luogu2744 量取牛奶
  5. 【转载】java学习线路
  6. 【TJOI 2018】数学计算
  7. ie8 js编译器对象为空或不是对象的一个小问题
  8. jquery得到焦点和失去焦点
  9. poj3264Balanced Lineup(倍增ST表)
  10. [Swift通天遁地]八、媒体与动画-(8)使用开源类库快速实现位移动画