A Bug's Life hdu1829 并查集

    本题为二分的并查集，其实只要在原先的并查集基础上作一下变形。当然此题也还是有技巧的，我们可以对每个节点做个标记，若该节点与父亲节点属于同一类，则标记为,0，否则标记为1。但当我们合并两棵树时，可能会存在两棵树的标记所表达的意思完全相反，此时我们就要通过改变其中一棵树根节点的标记，来保持合并之后的树保持一致。
 
至于何时有同性恋发生，应该不难判断了，若两个节点属于同一棵树且属于同一类则发生同性恋。
 
[cpp] 
#include<iostream>  
#include<cstdio>  
  
using namespace std;  
const int maxn=2005;  
int set[maxn],flag[maxn];  
//set[i]记录i的父亲节点，flag[i]==0表示该节点的性别与父亲节点相同，否则不相同  
  
void init(int n)  
{  
    for(int i=1;i<=n;i++)  
    {  
        set[i]=i;  
        flag[i]=0;  
    }  
}  
  
int find1(int x)//返回父亲节点  
{  
    while(set[x]!=x)  
        x=set[x];  
    return x;  
}  
  
int find2(int x)//返回0或1，判断该节点与根节点是否一致  
{  
    int t=0;  
    while(set[x]!=x)  
    {  
        t^=flag[x];  
        x=set[x];  
    }  
    return t;  
}  
  
bool merge(int x,int y)//合并  
{  
    int f1=find1(x);  
    int f2=find1(y);  
    if(f1==f2)  
        return false;  
    set[f1]=f2;  
    //如果两棵树定义有冲突，则使它们一致（此处通过改变flag[f1]）  
    if(find2(x)==find2(y))  
        flag[f1]^=1;  
    return true;  
}  
  
int main()  
{  
    int t,n,m,a,b,C=1;  
    bool state;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d%d",&n,&m);  
        init(n);  
        state=true;  
        while(m--)  
        {  
            scanf("%d%d",&a,&b);  
            if(!state)  
                continue;  
            if(!merge(a,b)&&(find2(a)^find2(b))==0)//同一棵树且性别相同的两个节点  
                state=false;  
        }  
        printf("Scenario #%d:\n",C++);  
        if(!state)  
            printf("Suspicious bugs found!\n");  
        else  
            printf("No suspicious bugs found!\n");  
        printf("\n");//每个样例后面都换行，坑爹的地方  
    }  
    return 0;  
}

补充：软件开发 , C++ ,