poj2492 750ms 解法二：带权并查集

#include<cstdio>
using namespace std;
const int Maxn = 2019;
int rel[Maxn],father[Maxn];
//0表示同性，1表示异性
//参考网上的第二种解法，也就是带权(种类)并查集
void init(int n)
{
    for(int i = 1; i<=n; ++i)
    {
        father[i] = i;
        rel[i] = 0;
    }
}
int find(int x)
{
    if(x!=father[x])
    {
        int px = find(father[x]);
        rel[x] = rel[x]^rel[father[x]];//若x与父节点的权值不一样，则x与父节点性别不同，难点
        father[x] = px;
    }
    return father[x];
}
int _union(int a,int b)
{
    int x = find(a);
    int y = find(b);
    if(x==y)
    {
        if(rel[a]==rel[b])
            return 1;
        return 0;
    }
    else
    {
        father[x] = y;
        rel[x] = !(rel[a]^rel[b]);
    }
    return 0;
}
int main()
{
    int t,n,m;
    int a,b;
    scanf("%d",&t);
    for(int i = 1; i<=t; ++i)
    {
        scanf("%d%d",&n,&m);
        bool f = false;
        init(n);
        while(m--)
        {
            scanf("%d%d",&a,&b);
            if(!f&&_union(a,b))
                f = true;
        }
        printf("Scenario #%d:\n",i);
        puts(f?"Suspicious bugs found!\n":"No suspicious bugs found!\n");
    }
    return 0;
}