#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 閱讀(195)
評論(0) 編輯 收藏 引用