HDU 1829 A Bug's Life(基础种类并查集)

2023-12-10 04:48

本文主要是介绍HDU 1829 A Bug's Life(基础种类并查集),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链接:

http://acm.hdu.edu.cn/showproblem.php?pid=1829


原题:

Problem 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
  
2 3 3 1 2 2 3 1 3 4 2 1 2 3 4

Sample Output
  
Scenario #1: Suspicious bugs found!Scenario #2: No suspicious bugs found!
Hint
Huge input,scanf is recommended.


分析与总结:

做了这题才再次发现自己对并查集的了解真的只是一些皮毛,并查集的很多高级应用我都还不懂,而这题只是种类并查集中最简单的  = =|||。


假设有

1,2

2,3

即1--2--3, 明显相邻的两个不能是同性别的,如果相邻两个是同性的,那么说明就可能是有同性恋存在。

上面假设1是男性,用false来代替,那么按顺序分别是false, true, false

假设  再加个关系3, 1

那么由于1和3已经都有值了,都是false,说明可能有同性恋。


种类并查集的关键在于与结点与根结点的距离, 如果距离是奇数那么性别就和跟结点相反,如果是偶数就和跟结点性别相同。



代码:

#include<cstdio>
#define N 2005
using namespace std;
int f[N],rank[N], n, k;
bool flag;inline void init(){flag=false;for(int i=0; i<=n; ++i)f[i]=i, rank[i]=0;
}
int find(int x){if(x==f[x])return f[x];int t=find(f[x]);rank[x] = (rank[f[x]]+rank[x])&1;f[x]=t;return f[x];
}
void Union(int x, int y){int a=find(x), b=find(y);if(a==b){if(rank[x]==rank[y])flag=true;return;}f[a]=b;rank[a] = (rank[x]+rank[y]+1)&1;
}int main(){int T,a,b,cas=1;scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);init();for(int i=0; i<k; ++i){scanf("%d%d",&a,&b);if(flag)continue;Union(a,b);}printf("Scenario #%d:\n",cas++);if(flag)printf("Suspicious bugs found!\n");else printf("No suspicious bugs found!\n");printf("\n");}return 0;
}



——  生命的意义,在于赋予它意义。

          
     原创 http://blog.csdn.net/shuangde800 , By   D_Double  (转载请标明)




这篇关于HDU 1829 A Bug's Life(基础种类并查集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/476053

相关文章

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

前端bug调试的方法技巧及常见错误

《前端bug调试的方法技巧及常见错误》:本文主要介绍编程中常见的报错和Bug,以及调试的重要性,调试的基本流程是通过缩小范围来定位问题,并给出了推测法、删除代码法、console调试和debugg... 目录调试基本流程调试方法排查bug的两大技巧如何看控制台报错前端常见错误取值调用报错资源引入错误解析错误

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型,3步搞定一个应

Android里面的Service种类以及启动方式

《Android里面的Service种类以及启动方式》Android中的Service分为前台服务和后台服务,前台服务需要亮身份牌并显示通知,后台服务则有启动方式选择,包括startService和b... 目录一句话总结:一、Service 的两种类型:1. 前台服务(必须亮身份牌)2. 后台服务(偷偷干

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面:幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件

使用Python实现生命之轮Wheel of life效果

《使用Python实现生命之轮Wheeloflife效果》生命之轮Wheeloflife这一概念最初由SuccessMotivation®Institute,Inc.的创始人PaulJ.Meyer... 最近看一个生命之轮的视频,让我们珍惜时间,因为一生是有限的。使用python创建生命倒计时图表,珍惜时间