A Bug's Life
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6168 Accepted Submission(s): 2000
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.
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.
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.
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!HintHuge input,scanf is recommended.
Source
Recommend
linle
这个题目一看就知道可能是用并查集来做，但是和普通的并查集又有点不同，第一次做的时候没做出来，今天看了看就做出来了
下面的代码没有优化，在做的时候发现数据量不是很大，就想用随便一点的代码直接实现，猜想这个题目就是考并查集，只要想
出来了一般是不会卡你时间的
思想：
首先建立两个数组，一个是rec这个是专门用来并查的，还有一个是sex这个是用来记录相应编号的某一异性的编号
当输入两个虫的编号的时候首先判断这两个虫是否都有异性，如果有就把能确定性别的放在一起
也就是这样一个思路，输入a和b，那么判断a有没有能确定的异性，如果有，那么将b所在统一性别的群体和a的异性所在的群体
并到一起，a b是等价的，同样对b进行相同的操作！
最后完成之后查询a 和 b 是否在同一个集合中，如果是那么就发现了同性恋，否则没有！
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int rec[5000];
int sex[5000];
int init(int n)
{
int i;
for(i=0;i<=n;i++)
rec[i]=sex[i]=i;
return 0;
}
int find_root(int x)
{
while(rec[x] != x)
{
x=rec[x];
}
return x;
}
int union_set(int x,int y)
{
int a=find_root(x);
int b=find_root(y);
if(a < b)
rec[b]=a;
else
rec[a]=b;
return 0;
}
int main()
{
int t,i,j,n,m;
bool flag;
scanf("%d",&t);
int a,b;
int k=0;
while(t--)
{
k++;
flag=false;
scanf("%d%d",&n,&m);
init(n);
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
if(flag)
continue;
if(sex[a]==a)
sex[a]=b;
else
union_set(b,sex[a]);
if(sex[b]==b)
sex[b]=a;
else
union_set(a,sex[b]);
if(find_root(a) == find_root(b))
flag=true;
}
printf("Scenario #%d:\n",k);
if(flag)
printf("Suspicious bugs found!\n");
else
printf("No suspicious bugs found!\n");
if(t>0)
printf("\n");
}
return 0;
}