与POJ-1703类似。。故先转一个和1703相同解法的代码：
————————————————————
【转】
这道题和poj1182是很类似的，只不过拿那道题目有三个集合，而我们这道只有两个，岂不是更简单！
具体做法要在熟悉了并查集这种数据结构的常规操作之后进行扩展。
关于并查集请参考《算法导论》，这是一本非常非常出色的算法类参考书，他所讲的不相交集合就是并查集。
注意两个概念：按秩合并、路径压缩。
1、按秩合并
由于并查集一般是用比较高效的树形结构来表示的，按秩合并的目的就是防止产生退化的树（也就是类似链表的树），用一个数组记录各个元素的高度（也有 的记录各个元素的孩子的数目，具体看哪种能给解题带来方便），然后在合并的时候把高度小的嫁接到高度大的上面，从而防止产生退化的树。
2、路径压缩
而另一个数组记录各个元素的祖先，这样就防止一步步地递归查找父亲从而损失的时间。因为并查集只要搞清楚各个元素所在的集合，而区分不同的集合我们用的是代表元素（也就是树根），所以对于每个元素我们只需保存其祖先，从而区分不同的集合。
而我们这道题并没有使用纯正的并查集算法，而是对其进行了扩展，
我们并没有使用“1、按秩合并”（当然你可以用，那样就需要再开一个数组）
我们从“1、按秩合并”得到启示，保存“秩”的数组保存的是元素相对于父节点的关系，我们岂不可以利用这种关系（即相对于父节点的不同秩值来区分不同的集合），从而可以把两个集合合并成一个集合。（注：此代码 rank=0 代表 和父节点同一性别）
#include<stdio.h>
int f[2005],r[2005];
int fs(int i)
{
if(f[i]==i)
return i;
int t=f[i];
f[i]=fs(f[i]); //路径压缩技术，使f[i]直接指向最新的根节点
//计算相对于新的父节点（即根）的秩，r[t]是老的父节点相对于新的父节点（即根）的秩，r[i]是i元素相对于老的父节点的秩，
//类似于物理里的相对运动，得到的r[i]就是相对于新的父节点（即根）的秩。而且这个递归调用不会超过两层。
r[i]=(r[t]+r[i])%2;
return f[i];
}
void un(int x,int y)
{
int a=fs(x),b=fs(y);
f[a]=b;
r[a]=(r[y]-r[x]+1)%2; //r[a]+r[x]与r[y]相对于新的父节点必须相差1个等级，因为他们不是gay
}
int main()
{
freopen("in.txt","r",stdin);
int cases,n,m,i,k,x,y;
scanf("%d",&cases);
for(k=1;k<=cases;k++)
{
int flag=0;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
f[i]=i;
r[i]=0;
}
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
if(fs(x)==fs(y))
{
if(r[x]!=(r[y]+1)%2)
flag=1;
}
else
un(x,y);
}
if(flag)
printf("Scenario #%d:\nSuspicious bugs found!\n\n",k);
else
printf("Scenario #%d:\nNo suspicious bugs found!\n\n",k);
}
return 0;
}
————
本题还有一种比较直观的解法：即把不同性别的bug放在不同的集合里（此解法对1703 ms不太实用）
：
#include <cstdio>
#include <cstring>
using namespace std;
const int maxBugNum = 2000 + 5;
int sceNum, bugNum, actNum;
int p[maxBugNum], h[maxBugNum], G[maxBugNum][maxBugNum];// p， h ：并查集的域
void makeSet(int i){
p[i] = i; h[i] = 1;
}
int findSet(int i){ //路径压缩
if(i != p[i])
p[i] = findSet(p[i]);
return p[i];
}
void unionSet(int lhs, int rhs){
lhs = findSet(lhs); rhs = findSet(rhs);
if(h[lhs] > h[rhs]) //按秩合并
p[rhs] = lhs;
else{
p[lhs] = rhs;
if(h[lhs] == h[rhs]) h[rhs]++;
}
}
void print(int num, bool flag){
printf("Scenario #%d:\n", num);
if(flag)
printf("Suspicious bugs found!\n");
else
printf("No suspicious bugs found!\n");
if(num < sceNum) printf("\n");
}
int main(){
scanf("%d", &sceNum);
for(int i=1; i<=sceNum; i++){
memset(G, 0, sizeof(G));
scanf("%d%d", &bugNum, &actNum);
for(int j=1; j<=bugNum; j++)
makeSet(j);
int u, v;
bool flag = 0;
for(int j=0; j<actNum; j++){
scanf("%d%d", &u, &v);
G[u][v] = G[v][u] = 1;
}
//所有G[u][v]==1 的 v都应该是同一性别， 合并之
//如果G[u][v]==1 而且 u 和 v 在同一集合， 则同性恋
for(u=1; u<=bugNum; u++){
int first = -1;
for(v=1; v<=bugNum; v++){
if(G[u][v]){
if(first == -1) first = v;
if(findSet(u) == findSet(v)){
flag = 1; break;
}
else if(first != -1){
unionSet(first, v);
}
}
}
}
print(i, flag);
}
return 0;
}
————