poj 2492

题意：Professor Hopper专门研究bug的生活习性，他表示若两只bugs的生活习性差别很大，则说明他们可能为不同的性别，但如果出现三只bugs的习性两两差别很大，则有可能出现同性恋的bug了。现在有n只bugs，和生活习性差别很大的m对bugs的编号，问这些bugs中，有没有可能出现同性恋者。题目中给出的数对比如（1 2 ，2 3 ，1 3）是表示交配关系的，而且交配的都默认为理解为异性，这里如果有矛盾的情况，就表明有同性恋存在。比如1和2是异性，2和3为异性，那就表明1和3是同性，但是给出的数对是1和3异性表明有矛盾存在，则有同性恋存在，则输出Suspicious bugs found。

 

代码如下：

 

#include<iostream>
using namespace std;
const int Max = 2005;

int n, m;
int parent[Max], opp[Max];

void make_set()
{
    for(int x = 1; x <= n; x ++)
	{
        parent[x] = x;
        opp[x] = 0;
    }
}



int find_set(int x)
{
    if(x != parent[x])
        parent[x] = find_set(parent[x]);
    return parent[x];
}



void union_set(int x, int y)
{
    x = find_set(x);
    y = find_set(y);
    if(x == y)
		return;
    parent[y] = x;
}



int main()
{
    int t, i, x, y;
    scanf("%d", &t);
    for(i = 1; i <= t; i ++)
	{
        scanf("%d %d", &n, &m);
        make_set();
        bool flag = false;
        while(m--)
		{
            scanf("%d %d", &x, &y);
            if(flag) 
				continue;
            if(find_set(x) == find_set(y))
			{  // 若x，y同在一个集合，则证明有同性的可疑。
                flag = true;
            }
            if(opp[x] == 0 && opp[y] == 0)
			{
                opp[x] = y;//表明y是x的异性
                opp[y] = x;
            }
            else if(opp[x] == 0)
			{
                opp[x] = y;
                union_set(x, opp[y]);
            }
            else if(opp[y] == 0)
			{
                opp[y] = x;
                union_set(y, opp[x]);
            }
            else
			{
                union_set(x, opp[y]);
                union_set(y, opp[x]);
            }
        }
        printf("Scenario #%d:\n", i);
        if(flag) 
			printf("Suspicious bugs found!\n\n");
        else 
			printf("No suspicious bugs found!\n\n");
    }
    return 0;
}