题意：有n只虫子，每次给出一对互为异性的虫子的编号，输出是否存在冲突。
思路：用并查集，每次输入一对虫子后就先判定一下。如果两者父亲相同，则说明关系已确定，再看性别是否相同，如果相同则有冲突。否则就将两只虫子并入一个集合。
而性别则是用一个gender数组来维护，每个虫子的gender的值为0或者1。
0表示该虫子的性别与父亲结点的性别相同。
1表示该虫子的性别与父亲结点的性别不同。
这题和poj1703本质上是一样的。1703的题解请点传送门。
另外还有一个疑惑，本题输入量巨大，我用输入加速后反而比用scanf要慢得多，弄不明白为什么。。有知道的大神欢迎来给解答一下。
#include<stdio.h>
#define maxn 2010
int father[maxn], gender[maxn];
int Find(int x)
{
if (father[x] != x)
{
int t = father[x];
father[x] = Find(father[x]);
gender[x] = (gender[x] + gender[t]) % ;
}
return father[x];
}
void Merge(int x,int y)
{
int fx = Find(x);
int fy = Find(y);
father[fx] = fy;
if (gender[y] == )
gender[fx] = ^ gender[x];
else gender[fx] = gender[x];
}
int main()
{
int t;
int cas = ;
//freopen("data.in", "r", stdin);
scanf("%d",&t);
while (t--)
{
int n, m;
scanf("%d%d",&n,&m);
for (int i = ; i <= n; i++)
{
father[i] = i;
gender[i] = ;
}
int ok = ;
while (m--)
{
int a, b;
scanf("%d%d",&a,&b);
if (!ok) continue;
if (Find(a) != Find(b))
Merge(a, b);
else if(gender[a] == gender[b])
ok = ;
}
if (ok) printf("Scenario #%d:\nNo suspicious bugs found!\n\n", cas++);
else printf("Scenario #%d:\nSuspicious bugs found!\n\n", cas++);
}
return ;
}