#include<iostream>
using namespace std;
#define mx 2000
struct
{
int rank;
int parent;
int opposite; //与自己不同性的某一虫子，初始化时为自己
}bugs[mx];
void Make_set(int n);
int Find_set(int x);
void Union(int x,int y);
int main()
{
int ts;//测试数据的数量
scanf("%d",&ts);
int t=1;
while(ts--)
{
int bugnum/*虫子数*/,pairs/*研究的对数*/;
scanf("%d%d",&bugnum,&pairs);
Make_set(bugnum);
int i;
int m,f;
bool IsFound=false;
int a,b;
for(i=0;i<pairs;i++)
{
scanf("%d%d",&m,&f);//m号虫，f号虫
a=Find_set(m-1);
b=Find_set(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++);
}
//system("pause");
return 0;
}
void Make_set(int n) //初始化，产生n个集合，每个集合一只虫
{
int i;
for(i=0;i<n;i++)
{
bugs[i].rank=0;
bugs[i].parent=i;
bugs[i].opposite=i;
}
}
int Find_set(int x) //寻找根节点，路径压缩
{
if(x!=bugs[x].parent)
bugs[x].parent=Find_set(bugs[x].parent);
return bugs[x].parent;
}
void Union(int x,int y) //合并相同集合，按秩合并
{
int a=Find_set(x);
int b=Find_set(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++;
}
posted on 2009-06-30 15:43
luis 阅读(176)
评论(0) 编辑 收藏 引用