#include<iostream>
using namespace std;
#define mx 2000
struct
{
int rank;
int parent;
int opposite; //與自己不同性的某一蟲子，初始化時(shí)為自己
}bugs[mx];
void Make_set(int n);
int Find_set(int x);
void Union(int x,int y);
int main()
{
int ts;//測(cè)試數(shù)據(jù)的數(shù)量
scanf("%d",&ts);
int t=1;
while(ts--)
{
int bugnum/*蟲子數(shù)*/,pairs/*研究的對(duì)數(shù)*/;
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號(hào)蟲，f號(hào)蟲
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是自己（既未被設(shè)置），則設(shè)為對(duì)方。
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) //初始化，產(chǎn)生n個(gè)集合，每個(gè)集合一只蟲
{
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) //尋找根節(jié)點(diǎn)，路徑壓縮
{
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 閱讀(199)
評(píng)論(0) 編輯 收藏 引用