问题传送门：

题意：

某种动物有两种性别，只有异性才能交往。
一共 n 个动物，m 个关系。
每个关系表示 a 和 b 在交往。
输入有 t 组数据。
对于每组数据的 m 个关系，判断其中有没有同性恋。

默认先出现的关系是异性的。

分析：

一开始想的是，直接对交往的人进行并查集，当遇到两个人交往
但是在同一个集合中时，就是有同性恋。
仔细想想当然是错误的。

这个题还是带权并查集：
用 0 表示与根节点性别相同，
用 1 表示与根节点性别不同，
初始 rel[i] = 0.
当判断一个新的关系时，
如果不在同一个集合，默认是异性，可以交往。
如果在同一个集合， 通过根节点计算他们的性别关系。

代码：

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 2000+10;
int R[MAXN];
int rel[MAXN];

void init(int n, int &f)
{
	f = 0;
	for (int i = 0; i <= n; i++)
		R[i] = i, rel[i] = 0;
}

int Find(int x)
{
	if (x == R[x])
		return R[x];
	else {
		int t = R[x];
		R[x] = Find(R[x]);
		rel[x] = (rel[x] + rel[t]) % 2;
		return R[x];
	}
}

bool Join(int a, int b)
{
	int ra = Find(a);
	int rb = Find(b);
	if (ra != rb) {
		R[ra] = rb;
		rel[ra] = (1+2+rel[b]-rel[a]) % 2;
		return true;
	}
	return false;
}

int main()
{
	int T, n, m, a, b, f;
	cin >> T;
	for (int i = 1; i <= T; i++)
	{
		cin >> n >> m;
		init(n, f);
		while (m--)
		{
			scanf("%d %d", &a, &b);
			if (!Join(a, b) && (rel[a]-rel[b]+2)%2==0)
				f = 1;
		}
		cout << "Scenario #" << i << ":" << endl;
		if (f)
			cout << "Suspicious bugs found!" << endl;
		else
			cout << "No suspicious bugs found!" << endl;
		cout << endl;
	}
	return 0;
}