?本题为二分的并查集，其实只要在原先的并查集基础上作一下变形。当然此题也还是有技巧的，我们可以对每个节点做个标记，若该节点与父亲节点属于同一类，则标记为,0，否则标记为1。但当我们合并两棵树时，可能会存在两棵树的标记所表达的意思完全相反，此时我们就要通过改变其中一棵树根节点的标记，来保持合并之后的树保持一致。
?
至于何时有同性恋发生，应该不难判断了，若两个节点属于同一棵树且属于同一类则发生同性恋。
?
[cpp] ?
#include ?
#include ?
??
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; ? www.2cto.com
? ? ? ? } ?
? ? ? ? printf("Scenario #%d:\n",
C++); ?
? ? ? ? if(!state) ?
? ? ? ? ? ? printf("Suspicious bugs found!\n"); ?
? ? ? ? else ?
? ? ? ? ? ? printf("No suspicious bugs found!\n"); ?
? ? ? ? printf("\n");//每个样例后面都换行，坑爹的地方 ?
? ? } ?
? ? return 0; ?
} ?
?