poj2492 766ms 带权并查集

#include<cstdio>
#include<cstring>
using namespace std;
//带权并查集其一解法
//敌人的敌人就是朋友
const int Maxn = 2000;
int father[Maxn<<1];
void init(int n)
{
    for(int i = 1; i<=2*n; ++i)
        father[i] = i;
}
int find(int x)
{
    return x==father[x] ? x : father[x] = find(father[x]);
}
void _union(int a,int b)
{
    int x = find(a);
    int y = find(b);
    if(x!=y)
        father[x] = y;
}
int main()
{
    int t,n,m;
    int a,b;
    scanf("%d",&t);
    for(int i = 1; i<=t; ++i)
    {
        scanf("%d%d",&n,&m);
        init(n);
        bool f = false;
        while(m--)
        {
            scanf("%d%d",&a,&b);
            if(f)
                continue;
            if(find(a)==find(b))
                f = 1;
            else
            {
                _union(a,b+n);
                _union(a+n,b);
            }
        }
        printf("Scenario #%d:\n",i);
        puts(f?"Suspicious bugs found!":"No suspicious bugs found!");
        printf("\n");
    }
    return 0;
}