POJ1611 The Suspects (并查集)
发布日期:2021-08-29 23:31:56 浏览次数:15 分类:技术文章

本文共 2284 字,大约阅读时间需要 7 分钟。

本文出自:

题意:0号学生染病,有n个学生,m个小组。和0号学生同组的学生染病,病能够传染。

            输入格式:n,m

                                数量  学生编号1,2,3,4

                                //m个分组

题解:最为典型的并查集。

     解法一:求出全部的集合,然后求出0的parent,把parent为0的parent全部学生求出。

     解法二:在计算的过程中统计total;

解法一:(一開始用的Vim写的在POJ上交出现 訪问禁止错误- - 不知道又奇妙的碰上了什么BUG,删了main函数中几个换行符就好了)

#include 
#include
using namespace std;int stu[30001];//the num of stu, groupint n, m;void init(){ for(int i = 0; i < n; i++) stu[i] = i;}int getParent(int a){ if(a == stu[a]) return a; else return stu[a] = getParent(stu[a]);}void Merge(int a, int b){ if(getParent(a) == getParent(b)) return; else stu[getParent(a)] = b;}int main(){ int i, j; int deter, sum; int num; int temp1, temp2; while(scanf("%d%d", &n, &m)) { if(n == 0 && m == 0) break; init(); for(i = 0; i < m; i++) { scanf("%d", &num); scanf("%d", &temp1); for(j = 1; j < num; j++) { scanf("%d", &temp2); Merge(temp1, temp2); } } deter = stu[getParent(0)]; sum = 1; for(i = 1; i < n; i++) { if(getParent(i) == deter) sum++; } printf("%d\n", sum); } return 0;}

解法二:

#include 
#include
using namespace std;int stu[30001];int total[30001];//the num of stu, groupint n, m;void init(){ for(int i = 0; i < n; i++) { stu[i] = i; total[i] = 1; }}int getParent(int a){ if(a == stu[a]) return a; else return stu[a] = getParent(stu[a]);}void merge(int a, int b){ if(getParent(a) == getParent(b)) return; else { total[getParent(a)] += total[getParent(b)]; stu[getParent(b)] = a; }}int main(){ int i, j; int num;//record the group's num int temp1, temp2; while(scanf("%d%d", &n, &m)) { if(n == 0 && m == 0) break; init(); for(i = 0; i < m; i++) { scanf("%d", &num); scanf("%d", &temp1); for(j = 1; j < num; j++) { scanf("%d", &temp2); merge(temp1, temp2); } } printf("%d\n", total[getParent(0)]); //不能直接stu[0],由于stu[0]不一定是根节点。 } return 0;}

转载地址:https://blog.csdn.net/weixin_34015336/article/details/85689276 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:9. 星际争霸之php设计模式--代理模式
下一篇:电脑杀毒的常用方法(转)

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月27日 05时25分02秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

androdi Studio 51 mp3 2019-04-21
android studio 52 mp3下载客户端001 2019-04-21
android studio 53 mp3 2019-04-21
Android studio 53 文件下载 2019-04-21
android studio 54 下载进度条 2019-04-21
android studio 70 歌曲服务器搭建 歌曲app 完整代码(发布版) 2019-04-21
Android单击事件处理与监听003 2019-04-21
java sqlite 建表语句_SQLite不能创建表 2019-04-21
java数据流转化为图片_输出流读取文件内容转换为图片 2019-04-21
java输入格式_JAVA自学笔记: 利用循环设计当用户输入格式错误的时候重新输入... 2019-04-21
qt界面黑的咋办_关于 Qt设置置顶窗口,透明部分显示黑色底色(已设置透明窗口) 的解决方法... 2019-04-21
tpl怎么搞_emlog后台模板设置功能插件tpl_options 2019-04-21
linux巡检脚本shell,linux系统巡检脚本一枚 2019-04-21
红帽linux如何设置3d桌面,LINUX怎么设置3D桌面? 2019-04-21
linux下的free函数,Linux vmalloc/vfree函数实现解读 2019-04-21
手动搭建Linux云服务器,Linux系统云服务器怎么手动搭建 FTP 服务?四步搞定。 2019-04-21
parrot linux桌面设置,parrot使用一些技巧 2019-04-21
linux 管道统计文件,科学网—[转载]Linux管道命令之文件与文件夹统计 - 高琳琳的博文... 2019-04-21
读文件程序一行的函数c语言,c fgets()函数 读取文件时位置会自动移动下一行吗?该如何处理... 2019-04-21
老船履带工具使用方法_电流表工具的正确使用方法 2019-04-21