A Bug's Life POJ - 2492

2
3 3
1 2
2 3
1 3
4 2
1 2
3 4

Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!

Huge input,scanf is recommended.

思路：这题比较好理解，用x+n来表示能与x交配的所有编号的虫子，如果发现两个互相交配的虫子AB同时可以交配同一个虫子C，那证明有homo虫。

#include <stdio.h>
int parent[2005+2005];
int find(int x)
{
    return (x==parent[x])?x:parent[x]=find(parent[x]);
}
void init(int a)
{
    for(int i=1;i<=2*a;i++)
        parent[i]=i;
}
int same(int x,int y)
{
    return find(x)==find(y);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y) return ;
    else    parent[y]=x;
}
int main(void)
{


    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
        {
        int flag=0;
        int amount,pair;
        scanf("%d%d",&amount,&pair);
        init(amount);
        for(int i=1;i<=pair;i++)
        {
            int num1,num2;
            scanf("%d%d",&num1,&num2);
            if(same(num1,num2)==1)  
                flag=1;
            else
                unite(num1+amount,num2),unite(num1,num2+amount); // 关键
        }
        if(flag)
            printf("Scenario #%d:\nSuspicious bugs found!\n\n",i);
        else
            printf("Scenario #%d:\nNo suspicious bugs found!\n\n",i);
    }
}