A Bug's Life
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5301 Accepted Submission(s): 1742
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.
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.
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!HintHuge input,scanf is recommended.
Source
Recommend
linle
解题思路：并查集的题目，断断续续困扰了我一个星期，还查了不少解题报告，问题的关键是如何判定两只虫子的性别，这里用了sex和father两个数组，若sex数组为0，即是该该虫子的性别尚未确认，则设后输入的虫子的性别与先输入的虫子的性别相反，两个都不确定就是互反；如果一只虫子的性别已经得到确认，找到与之相同性别的所有虫子（利用sex数组找到输入的另一只虫子的异性，再递归找到此异性的所有同性，并更新这些同性指向同一最远公共祖先，也可理解为把他们合并至同一集合），把同一性别的虫子的father都指向他们的最远祖先（比如1,2,3都是雄性，则在递归更新中father[2]=father[3]=1），这时，如果新输入的两只虫子有相同的最远祖先，他们就是同性恋。（ps:按这一题的说法,三角恋中必定有同性恋存在，囧，=
=!）
=!）
#include <iostream>
#include<cstring>
using namespace std;
int father[2010],sex[2010],a,b;
void initial()
{
int i;
for(i=0;i<2010;i++)
father[i]=i;
memset(sex,0,sizeof(sex));
}
int find(int x)
{
if(x==father[x])
return x;
else
return father[x]=find(father[x]);
}
int main()
{
long i,n,bug,line,t=1;
bool flag;
scanf("%ld",&n);
while(n--)
{
initial();
flag=false;
scanf("%ld%ld",&bug,&line);
for(i=0;i<line;i++)
{
scanf("%ld%ld",&a,&b);
if(flag)
continue;
int x=find(a);
int y=find(b);
if(x==y)//判定两只虫子是否有最远公共祖先，有的话就是在同一性别集合里，就是同性恋
flag=true;
if(sex[a]==0)//如果一只虫子未确定性别，设这种虫子性别与输入的另一只虫子性别相反
sex[a]=b;
else
{
int p=find(sex[a]);//找到并更新所有同一性别的虫子指向同一祖先，也就是把他们划到同一集合中
int q=find(b);
if(p!=q)
father[q]=p;
}
if(sex[b]==0)//同上
sex[b]=a;
else
{
int p=find(sex[b]);
int q=find(a);
if(p!=q)
father[q]=p;
}
}
if(flag)
printf("Scenario #%d:\nSuspicious bugs found!\n\n",t);
else
printf("Scenario #%d:\nNo suspicious bugs found!\n\n",t);
t++;
}
return 0;
}