变异并查集2223: A Bug's Life -CSDN博客

本文链接：https://blog.csdn.net/hqd_acm/article/details/5452712

Status	In/Out	TIME Limit	MEMORY Limit	Submit Times	Solved Users	JUDGE TYPE
	stdin/stdout	10s	8192K	383	86	Standard

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 Specification

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 Specification

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

Sample Output

Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!

Problem Source: TUD Contest 2005, Darmstadt, Germany

#include<stdio.h>
#define mx 2000
struct
{
       int rank;
       int parent;
       int opposite;   //与自己不同性的某一虫子，初始化时为自己
}bugs[mx];
void init(int n)   //初始化，产生n个集合，每个集合一只虫
{
     for(int i=0;i<n;i++)
     {
         bugs[i].rank=0;
         bugs[i].parent=i;
         bugs[i].opposite=i;
     }
}
int getfather(int x)   //寻找根节点，路径压缩
{
     if(x!=bugs[x].parent)
       bugs[x].parent=getfather(bugs[x].parent);
     return bugs[x].parent;
}
void Union(int x,int y)     //合并相同集合，按秩合并
{
     int a=getfather(x);
     int b=getfather(y);
     if(bugs[a].rank>bugs[b].rank)
         bugs[b].parent=a;
     else
         bugs[a].parent=b;
     if(bugs[x].rank==bugs[y].rank)
       bugs[y].rank++;
}
int main()
{
     int ts;//测试数据的数量
     scanf("%d",&ts);
     int t=1;
     while(ts--)
     {
       int bugnum/*虫子数*/,pairs/*研究的对数*/;
       scanf("%d%d",&bugnum,&pairs);
       init(bugnum);
       int i,m,f,a,b;
       bool IsFound=false;
       for(i=0;i<pairs;i++)
       {
           scanf("%d%d",&m,&f);//m号虫，f号虫
           a=getfather(m-1);
           b=getfather(f-1);
           if(a==b)//两只虫在同一集合中则有同性恋虫的怀疑
             IsFound=true;
           if(bugs[m-1].opposite!=m-1)//如果opposite中不是自己，则union(b,bugs[m-1].opposite
             Union(b/*f-1*/,bugs[m-1].opposite);
           else//如果opposite是自己（既未被设置），则设为对方。
             bugs[m-1].opposite=b;//f-1;
           if(bugs[f-1].opposite!=f-1)//同理
             Union(a/*m-1*/,bugs[f-1].opposite);
           else
             bugs[f-1].opposite=a;//m-1;
       }
      if(IsFound)
         printf("Scenario #%d:/nSuspicious bugs found!/n/n",t++);
       else
         printf("Scenario #%d:/nNo suspicious bugs found!/n/n",t++);
     }
     return 0;
}