A Bug's Life

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
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
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!
Hint
Huge input,scanf is recommended.

题目大意:给出许多虫子的交互,求这些虫子当中是否有gay，比如假设每个虫子交互时都是与异性交互，但是许多数据里面可能会出现问题，比如1 2交互，2 3 交互，所以1 3性别相同，如果再给出1 3交互，就错误了。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int t,n,m,flag,a1,a2;
int f[2010],sum[2010];//f存当前节点的父节点，sum存当前节点到根节点的距离
void init()//初始化数据
{
	for(int i=0;i<=n;i++)	f[i]=i;
	memset(sum,0,sizeof(sum));
	flag=0;
}
int find_root(int x)
{
	if(x!=f[x])
	{
		int temp=f[x];//先记录出这个父节点
		f[x]=find_root(f[x]);//压缩路径
		sum[x]+=sum[temp];//当前到父节点的距离，加上父节点到根节点的距离，就是这个节点到根节点的距离（动态规划的思想）
	}
	return f[x];//最后返回根节点
}
void union_set(int a,int b)
{
	int fa=find_root(a);
	int fb=find_root(b);
	if(fa!=fb)
	{
		f[fa]=fb;
		sum[fa]=sum[b]+1-sum[a];//简单画图即可推出
	}
	else if(sum[a]%2==sum[b]%2)	flag++;//如果根节点相同，判断稻根节点的距离mod2是否相等，如果相等就是gay
}
int main()
{
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		scanf("%d %d",&n,&m);
		init();
		while(m--)
		{
			scanf("%d %d",&a1,&a2);
			union_set(a1,a2);
		}
		cout<<"Scenario #"<<i<<':'<<endl;
		if(flag)	cout<<"Suspicious bugs found!"<<endl<<endl;
		else	cout<<"No suspicious bugs found!"<<endl<<endl;;
	}
	return 0;
}