POJ 2492 并查集扩展(判断同性恋问题)
发布日期:2021-08-19 01:52:42 浏览次数:1 分类:技术文章

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

G - A Bug's Life
Time Limit:10000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
Submit
Appoint description:

Description

Background
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.

Input

The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.

Output

The output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong.

Sample Input

23 31 22 31 34 21 23 4
3 4

Sample Output

Scenario #1:Suspicious bugs found!Scenario #2:No suspicious bugs found!

Hint

Huge input,scanf is recommended.
 
本题大概提议是给出n个bug和m对关系,每对关系都是异性进行的,问你是否有同性恋的关系
解决方法主要是路径压缩,还有怎么处理两个大的集合和如何去合并集合,我们应该把同性之间划分到一个集合里面
由于并查集其实就是一个构成的树,所以我们尽量在合并的时候将高度低的树合并到高度高的树中,我们在这里可以定义数组,rank
rank【x】代表的就是第x个节点所在树的高度,我们为了减少时间复杂度,尽量将高度低的节点转移到高度高的节点上去,这里判断一下rank的高低,之后用father【】数组合并就可以了
之后我们在定义个other数组,这个数组记录的是以自己为节点,之前和我匹配过得异性的节点:::例如other【x=3】=5,其实代表的就是我本身是节点3,我之前和5发生过关系,
这样处理的用处主要是加入后面3,和4再次配对的话,我们明显可以看出来,那么4和5属于同性关系,那么我们应该讲4,和5合并,如果other【3】!=0那么我们Union(otehr【3】,4),其实
也就是Union了(4,5);
 
解决此题的方法还有通过递归回溯的方法,别人的题解里,自己去看吧
 
1 #include
2 #include
3 #include
4 #include
5 using namespace std; 6 const int maxn=2005; 7 int father[maxn]; 8 int other[maxn]; 9 int rank[maxn];10 int m,n;11 12 void init(){13 for(int i=0;i<=n;i++){14 father[i]=i;15 rank[i]=0;16 other[i]=0;17 }18 }19 20 int get_father(int x){21 if(x!=father[x])22 father[x]=get_father(father[x]);23 return father[x];24 }25 26 void Union(int x,int y){27 int t1=get_father(x);28 int t2=get_father(y);29 if(rank[t1]>rank[t2])30 father[t2]=t1;31 else{32 father[t1]=t2;33 if(rank[t1]==rank[t2])34 rank[t2]++;35 }36 }37 38 int main(){39 int t;40 scanf("%d",&t);41 int cnt=1;42 while(t--){43 bool flag=false;44 scanf("%d%d",&n,&m);45 init();46 int x,y;47 for(int i=1;i<=m;i++){48 scanf("%d%d",&x,&y);49 int t1=get_father(x);50 int t2=get_father(y);51 if(flag)52 continue;53 if(t1==t2){54 flag=true;55 continue;56 }57 if(other[x]){58 Union(other[x],y);59 } 60 else61 other[x]=y;62 if(other[y])63 Union(other[y],x);64 else65 other[y]=x;66 67 }68 69 printf("Scenario #%d:\n",cnt++);70 if(flag)71 72 printf("Suspicious bugs found!\n");73 else74 printf("No suspicious bugs found!\n");75 puts("");76 }77 return 0;78 }

 

转载于:https://www.cnblogs.com/13224ACMer/p/5013760.html

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

上一篇:文件事件 时间事件
下一篇:(转)用户管理 之 Linux 用户(user)和用户组(group)管理概述

发表评论

最新留言

不错!
[***.144.177.141]2024年03月02日 04时31分54秒

关于作者

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

推荐文章

java 转发上传文件_java 后台请求其他接口转发文件 2019-04-21
Java get set 同步_java – getResultSet()“每个结果只能调用一次” 2019-04-21
java jmx 配置_为什么在配置JMX时Java打开3个端口? 2019-04-21
java thread回调_使用Runnable在Java中实现回调 2019-04-21
java 内存区_Java内存模型和Java内存区域的区别和联系? 2019-04-21
java定时任务监控_Spring定时任务使用及如何使用邮件监控服务器 2019-04-21
java crc32 使用_Java CRC32的用法 2019-04-21
java读取unicode_java怎么样将unicode解码读取?Java读取本地文件进 2019-04-21
java.io.file()_Java File getUsableSpace()方法 2019-04-21
java httpclient 工具_spring整合httpClient工具类 2019-04-21
java监控其他服务器运行状态_windows服务器监控多个tomcat运行状态 2019-04-21
java给学生按总成绩排名_java - 输入学生成绩,取它们的平均值,然后通过排名等级的学生 - SO中文参考 - www.soinside.com... 2019-04-21
java构造函数有什么用_java构造函数有什么用,怎么用 2019-04-21
mysql 匹配 隔开的_按空格分隔关键字并搜索MySQL数据库 2019-04-21
java factory用法_怎样使用Java实现Factory设计模式 2019-04-21
java窗口内容如何复制_求助Java窗口菜单如何实现复制粘贴剪切等功能(内附源代码)... 2019-04-21
盾神与砝码称重java_[蓝桥杯][算法提高VIP]盾神与砝码称重 2019-04-21
java输出狗的各类信息_第九章Java输入输出操作 2019-04-21
java notify怎么用_java 如何使用notify() 2019-04-21
java加载指定文件为当前文本,java:如何使用bufferedreader读取特定的行 2019-04-21