题意:
某种动物有两种性别,只有异性才能交往。
一共 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;
}
Comments | NOTHING