A Bug's Life POJ - 2492 (带权并查集)
2024-10-20 07:57:06
A Bug's Life POJ - 2492
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.
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.
题意:有一些群体的昆虫,两两一对,每一对都是在一起的,问给出的里面有没有同性恋的昆虫
题解:带权并查集,寻找与根节点的状态是否是一样的(是同性恋还是异性恋)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include<stack>
#include<map>
#include<cstdlib>
#include<vector>
#include<string>
#include<queue>
using namespace std; #define ll long long
#define llu unsigned long long
#define INF 0x3f3f3f3f
const double PI = acos(-1.0);
const int maxn = 5e4+;
const int mod = 1e9+; struct node
{
int pre;
int relation; //0:同 1:异
}p[maxn]; int find(int x)
{
int temp;
if(x == p[x].pre)
return x;
temp = p[x].pre;
p[x].pre = find(temp);
p[x].relation = (p[x].relation + p[temp].relation + ) % ;
return p[x].pre;
}
void combine(int x,int y)
{
int xx = find(x);
int yy = find(y);
if(xx != yy)
{
p[xx].pre = yy;
p[xx].relation = (p[y].relation - p[x].relation) % ;
}
}
int main()
{
int t;
scanf("%d",&t);
int ca=;
while(t--)
{
int n,m;
int flag = ;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
p[i].pre = i;
p[i].relation = ;
}
for(int i=;i<m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
if(find(a) == find(b))
{
if(p[a].relation == p[b].relation)
flag = ;
}
else
combine(a,b);
}
if(flag)
printf("Scenario #%d:\nSuspicious bugs found!\n\n",ca++);
else
printf("Scenario #%d:\nNo suspicious bugs found!\n\n",ca++);
}
}
最新文章
- GPS数据读取与处理
- 小米抢购(简单版v0.1)-登录并验证抢购权限,以及获取真实抢购地址
- SetForegroundWindow激活窗口
- 复杂sql分组查询 ( pivot)
- STM32F407 RCC时钟配置
- 嵌入式Linux驱动学习之路(三)u-boot配置分析
- 022医疗项目-模块二:药品目录的导入导出-对XSSF导出excel类进行封装
- js按钮点击展开收起
- Flash3D引擎:Away3D 4.1 Alpha版介绍
- JAVA并发实现四(守护线程和线程阻塞)
- IE浏览器中hasLayout的介绍
- 【LeetCode练习题】Minimum Depth of Binary Tree
- c#dalegate invoke及AsyncCallback使用
- Python连接SQLite数据库
- enzyme design 整体流程及感想
- Visual Studio 实用扩展工具
- 转载 .Net多线程编程—并发集合 https://www.cnblogs.com/hdwgxz/p/6258014.html
- springboot启动后总是自己shutdown
- 2018-2019-1 20189221《Linux内核原理与分析》第四周作业
- skynet对Windows环境支持的版本:Windows版skynet
热门文章
- JavaMail开发
- mysql连接error,Establishing SSL connection without server&#39;s identity verification is not recommended. According to MySQL 5.5.45+, 5.6.26+ and 5.7.6+ requirements SSL connection .....
- Arduino连接pH计
- ssm(Spring、Springmvc、Mybatis)实战之淘淘商城-第十一天(非原创)
- shrio中去掉 login;JSESSIONID
- linux 命令——12 more (转)
- Ajax的open方法
- IOS Quartz2D自定义view
- 如何解决EXCEL中的科学计数法
- java—三大框架详解,其发展过程及掌握的Java技术慨括