PAT_A1107#Social Clusters
Source:
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:
Ki: hi[1] hi[2] ... hi[Ki]
where Ki (>) 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 ;
}
最新文章
- 使用配置文件来配置JDBC连接数据库
- easyui dialog iframe
- 使用MiniProfiler跟踪MVC + EF + Bootstrap 2 权限管理系统的性能消耗
- 一个参数大小写引发的uploadify报错 ";Syntax error, unrecognized expression: #";
- python leetcode 日记--Maximal Square--221
- IIS网站服务器性能优化指南(转载)
- 【转】kylin优化
- jquery一些方法
- 嵌入dll到rtf文件
- Unity Shader Prpperties
- 【HDOJ】3505 Writing Robot
- (原)python中import caffe提示no module named google.protobuf.internal
- 启动及重新启动nginx,重启nginx后丢失nginx.pid问题解决
- ARPU_百度百科
- js获取当前日期,网页头部用
- Hibernate 异常 集锦
- 页面设计-数据列表 DataGrid
- git push 时提示用户名或密码相关错误信息
- delphi做的程序如何连接SQL数据库
- (84)Wangdao.com第十八天_JavaScript Promise 对象
热门文章
- [vs执行报错] CRT detected that the application wrote to memory after end of heap buffer
- 3.1 The Interpolating Polynomial(站点)
- ADT 压缩包 R23.0.0
- luogu2744 量取牛奶
- 【转载】java学习线路
- 【TJOI 2018】数学计算
- ie8 js编译器对象为空或不是对象的一个小问题
- jquery得到焦点和失去焦点
- poj3264Balanced Lineup(倍增ST表)
- [Swift通天遁地]八、媒体与动画-(8)使用开源类库快速实现位移动画