转载请注明出处：http://blog.csdn.net/u012860063?viewmode=contents

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1829

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

Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!

题目大意：Hopper教授正在研究一种稀有虫子的交配行为。他假设它们有两种性别并且它们只与异性交配。在他的实验中，很容易识别虫子和它们的交配行为，因为虫子背后印有编号。

问题
给定一组虫子的交配行为，确定实验是支持教授的假设即虫子没有同性恋，还是有部分交配行为不符合假设。

这道题实际上还是并查集，和以往不同的是。以往给出两个元素的关系，然后认为这两个元素有联系，把它们划归为同一个集合。   最后看看能划分出多少个不同的集合。 本道题，可以认为有两个集合，异性和同性。  给出关系，希望你检查这两个集合有没有连接，即有没有同性恋。
大体思路：   ‘合并’操作，  ‘查找’操作不变。设置一个sex[]   数组，sex[i]存储与 i  性别相反的对象编号 ,初始化为0 。 然后将于i  发生联系的元素合并为同一个集合（因为人为它们是同性）。下次输入x,y时，如果      find(x)==fidn(y)，我们就可以人为出现了反常行为。
总之，就是将同性的化为同一个集合中去。

代码如下：

#include <cstdio>
#include <cstring>
#define N 2017
int sex[N], set[N];
int find(int x)
{
    return x == set[x]?x:set[x]=find(set[x]);
}
void Union(int x, int y)
{
    int f1 = find(x);
    int f2 = find(y);
    if(f1 != f2)
    {
        set[f2] = f1;
    }
}
void init(int n)
{
    int i;
    for(i = 1; i <= n; i++)
    {
        set[i] = i;
        sex[i] = 0;
    }
}

int main()
{
	int n, m;
    int t, i, j;
    int x, y, cas = 0, flag;
    scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		init(n);
		flag = 0;
		for(i = 0; i < m; i++)
		{
			scanf("%d%d",&x,&y);
			if(flag)
				continue;
			if(find(x) == find(y))
			{
				flag = 1;
				continue;
			}    
			if(sex[x] == 0)
				sex[x] = y;
			else
				Union(sex[x],y);
			if(sex[y] == 0)
				sex[y] = x;
			else
				Union(sex[y],x);
		}
		printf("Scenario #%d:\n",++cas);
		if(flag)
			printf("Suspicious bugs found!\n");
		else
			printf("No suspicious bugs found!\n");
		printf("\n");
	}
    return 0;
}