hdu 1829 A Bug's Life(并查集)

A Bug's Life

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!  

题意：有N个小虫，编号1->N，给出M对交配的小虫编号,按理来说，应该是异性交配，但题目要求的就是是否会出现同性恋的情况，比如A和B交配，A,B是不同性别，B和C交配，B、C性别不同，如果A能和C交配，显然A，C是同性。

解析:并查集，将编号扩大两倍，1->N代表每个小虫，N+i代表i对应的另一性别的自己。对于每对编号a,b;先检查root(a)==root(b),如果相等，说明是同性恋，否则将root(a)与root(b+N)合并，root(b)与root(a+N)合并，相当于把同性的并在一起。

代码如下:

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<iterator>
#include<utility>
#include<sstream>
#include<iostream>
#include<cmath>
#include<stack>
using namespace std;
const int INF=1000000007;
const double eps=0.00000001;
int d[4005];
int root(int a)
{
    while(d[a]!=a) a=d[a];
    return a;
}
int main()
{
    int T,kase=0;
    cin>>T;
    while(T--)
    {
        int N,M;
        cin>>N>>M;
        for(int i=1;i<=2*N;i++)  d[i]=i;
        bool ok=true;
        for(int i=1;i<=M;i++)
        {
            int from,to;
            scanf("%d%d",&from,&to);
            if(!ok)  continue;
            int ra=root(from);
            int rb=root(to);
            if(ra==rb) ok=false;   //判断是否为同性恋
            ra=root(from);
            rb=root(to+N);
            d[ra]=rb;             //合并
            ra=root(from+N);
            rb=root(to);
            d[ra]=rb;
        }
        printf("Scenario #%d:
",++kase);

        if(!ok)  cout<<"Suspicious bugs found!"<<endl;
        else  cout<<"No suspicious bugs found!"<<endl;
        printf("
");
    }
    return 0;
}
View Code
 
 