(hdu step 5.1.1)A Bug's Life((ai,bi)表示ai、bi不在同一堆中,有若干對數據,判斷是否有bug)

題目：

A Bug's Life

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 723 Accepted Submission(s): 277 Problem DescriptionBackground
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. InputThe 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
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

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

Sample Output

Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!

HintHuge input,scanf is recommended. 

SourceTUD Programming Contest 2005, Darmstadt, Germany Recommendlinle

題目大意：

假設有這個兩組數據

1 2

1 3

name這時候得到的信息有以下三點：

1）1和2可以配對

2）1和3可以配對

3）2和3屬於同性,不能進行配對。也就是說不允許出現“2 3”這種數據

題目分析：

並查集。簡單題。通過上面的“題目大意”的理解。其實我們可以分析出美都區一堆數據" a b "的時候，

我們需要做以下操作：

1）判斷a和b的根節點是否相同。如果相同,則不符合題意(因為a b 表示的就是a與b的根節點不同)

2）判斷a是否已經由異性群.如果沒有,則為a建立異性群，即sex[a]=b。否則將b加入到a的異性群中。

代碼如下：

/*
 * a.cpp
 *
 *  Created on: 2015年2月26日
 *      Author: Administrator
 */

#include 
#include 


using namespace std;

const int maxn = 2001;

int father[maxn];//用於存儲父子關系.例如father[i]=i表示i的父親結點是他自己
int sex[maxn];//用於存儲配對關系.sex[a]=b表示a可以與吧配對

/**
 * 尋找a所在樹的根節點
 */
int find(int a){
	if(a == father[a]){//如果一個結點的父親節點是他自己
		return a;//則表示已經找到了根節點
	}

	return father[a] = find(father[a]);//否則繼續尋找。
}

/**
 * 合並a、b所在的兩棵樹
 */
void join(int a,int b){
	int fa = find(a);//找到a所在樹的根節點
	int fb = find(b);

	if(fa != fb){//如果a所在樹的根節點和b所在樹的根節點不相同,則證明a、b分別在兩顆不同的樹中
		father[fa] = fb;//合並a、b所在的兩棵樹
	}
}

/**
 * 初始化
 */
void init(){
	int i;
	for(i = 1 ; i < maxn ; ++i){//遍歷所有節點
		father[i] = i;//把每個節點的父親節點都指向他自己
	}
}

int main(){
	int t;
	scanf("%d",&t);
	int k;
	for(k = 1 ; k <= t ; ++k){
		int n;
		int m;

		init();
		memset(sex,0,sizeof(sex));//初始化配對關系.默認誰也沒有配對關系

		scanf("%d%d",&n,&m);
		int i;
		bool flag = true;//初始化是否有bug的標記.默認沒有bug
		for(i = 1 ; i <= m ; ++i){
			int a,b;
			scanf("%d%d",&a,&b);
			if(flag == true){//如果目前還沒有bug,則繼續建立新的關系
				int fa = find(a);//找到a的根節點
				int fb = find(b);//找到b的根節點

				if(fa == fb){//如果a與b在同一堆
					flag = false;//不符合題意.將flag標記為false,帶白哦有bug
					continue;
				}
				//如果能執行以下代碼,則代表a與b的關系正確

				if(sex[a] == 0){//如果a還沒有異性樹
					sex[a] = b;//給他建立一個異性群.目前這個群只有一個節點b
				}else{//如果a已經有異性群
					join(sex[a],b);//將b加入到異性群中
				}

				//對b執行同樣的操作
				if(sex[b] == 0){
					sex[b] = a;
				}else{
					join(sex[b],a);
				}
			}
		}


		printf("Scenario #%d:\n",k);
		if(flag == true){
			printf("No suspicious bugs found!\n");
		}else{
			printf("Suspicious bugs found!\n");
		}

//		if(k != t){//這種寫法居然還會PE。需要注意一下
			printf("\n");
//		}
	}

	return 0;
}