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

相关文章

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创建生命倒计时图表,珍惜时间

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和