A Bug's Life-----poj2492(关系并查集)

题目链接：http://poj.org/problem?id=2492

题意是问是否存在同性恋, 就是a喜欢b，b喜欢c，a又喜欢c，所以就有同性恋了；

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define N 11000
using namespace std;

int f[N], r[N];

int Find(int x)
{
    int k=f[x];
    if(x!=f[x])
    {
        f[x]=Find(f[x]);
        r[x]=(r[k]+r[x])%2;
    }
    return f[x];
}

int main()
{
    int T, n, m, i, t=1, x, y, flag;
    scanf("%d", &T);
    while(T--)
    {
        flag = 0;
        printf("Scenario #%d:
",t++);
        scanf("%d%d", &n, &m);
        for(i=0;i<n;i++)
        {
            f[i]=i;
            r[i]=0;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d", &x, &y);
            int px=Find(x), py=Find(y);
            if(px != py)
            {
                f[px]=py;
                r[px]=(2-r[x]+r[y]+1)%2;
            }
            else if(px==py && (r[y]-r[x]+2)%2!=1)
            {
                if(flag==0)
                {
                    printf("Suspicious bugs found!

");
                    flag=1;
                }
            }
        }
        if(flag==0)
            printf("No suspicious bugs found!

");
    }
    return 0;
}