当前位置：首页 > 编程日记 > 正文

1107 Social Clusters

编程日记 2024-09-06 17:50:00

这道题目给出的示例如上图所示，一共有1-8这8个人(圆形)，他们拥有1-10这10个兴趣爱好(方形)，一人可以有多个爱好，拥有共同爱好的人被视为一个社区的。现在给出每个人的爱好情况，求出社区的个数，并按照从大到小将社区的人数输出。

1. 起初我测试点1不通过，因为试图用一个vector<int> hobby[maxn]的数据结构，把每个社区的人的编号都读入，然后再和第一个人进行合并。实际上完全可以用int hobbyFirst[maxn]，将该社区的第一个人的编号读入，再有来者，把来着和这第一个人合并到同一社区即可。(边读入，边合并)

2. 这是并查集下的一道题，所以一定会有父亲数组F[maxn]，另外还开了一个数组number[maxn]，用于记录每个社区的人数(不需要知道每个社区有哪些人，只需要知道有多少人)，并且直接对其排序后输出。

3. 查找和合并函数要会写，没什么好说的，就是合并函数我起初写的时候最后一个不是把两个根节点合并，这点要注意。

AC代码

#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long LL;using namespace std;const int maxn = 1010;int F[maxn];//存放每个节点的父亲节点 
int number[maxn] = {0};//存放每个社区的人数 int findSource(int x){int a = x;while(x!=F[x]){x = F[x];}//压缩路径 while(a!=F[a]){int z = a;a = F[a];F[z] = x;	}return x;
}void unite(int a,int b){//将a和b所在的集合合并 int sa = findSource(a);int sb = findSource(b);if(sa!=sb){F[sa] = sb;}
}int main(){int n;//总人数 int hobbyFirst[maxn] = {0};//hobby[i]存放的是拥有i这个爱好的第一个人的编号 scanf("%d",&n);int num,idx;char c;//将所有人都初始化为根节点	for(int i=1;i<=n;i++){F[i] = i;}for(int i=1;i<=n;i++){scanf("%d:%c",&num,&c);//读入当前这个人的爱好个数 for(int j=0;j<num;j++){scanf("%d",&idx);//读入当前爱好编号 if(hobbyFirst[idx]==0)hobbyFirst[idx] = i;//如果这个爱好是第一次有人喜欢 else unite(i,hobbyFirst[idx]);//把当前这个人和拥有这个爱好的第一人放到同一个社区 }}for(int i=1;i<=n;i++){int sidx = findSource(i);number[sidx]++;//该社区的人数 }sort(number+1,number+1001);int lastIdx;for(int i=1000;i>=1;i--){if(number[i]==0){lastIdx = i;//997break;}} printf("%d\n",1000-lastIdx);for(int i=1000;i>lastIdx;i--){printf("%d",number[i]);if(i!=lastIdx+1)printf(" ");}return 0;
}

https://www.dkcj.cn/info/17568.html

1107 Social Clusters

相关文章：

c#直接调用ssis包实现Sql Server的数据导入功能

从入门到放弃的javaScrip——队列

css控制不换行

(C++)堆排序的3个关键函数

android 横竖屏限制如何配置

Java面试题总结-Day4

Linux 使用者身份與群組記錄的檔案

1098 Insertion or Heap Sort 需再做

基于node.js的压缩合并安装

jenkins 修改工作目录

破一个行业ERP的感想

1034 Head of a Gang(图的DFS解法) 擦边大法好

Android定位方式和测试方法

vue el-form鼠标事件导致页面刷新解决方案；vue 阻止多次点击提交数据通用方法...

[转]wxODBC(wxWidgets)中使用驱动程序方式打开数据库

1076 Forwards on Weibo

2014年个人工作总结

DAL(数据库访问层)

Navicat for Oracle

1013 Battle Over Cities(图的DFS解法)

你必须了解的微服务架构设计的10个要点！

企业信息化中常见决策点应对

WebView调试

1013 Battle Over Cities(并查集解法)

FastDFS为什么要结合Nginx？

STL容器[34]

企业可视化报表工具选型经验分享

1003 Emergency(Dijkstra，Bellman-Ford，SPFA三种解法)

存储过程4-前台

安卓学习-其他-文件读写