|
|
思路： 这题的背景是亮点，描述如下： Background
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.
Hopper 在研究某种稀有虫子的性行为。他假设虫子们有两种不同的性别，而且它们只跟异性发生关系。
在他的试验里，每个虫子和它的性行为都很容易辨认，因为它们的背后印着号码。
给出一些虫子的性行为，确定是否有同性恋的虫子能推翻这个假设。
同性恋确实让人无法接受，无论是人还是虫子。。
这题的解法不是亮点，就是普通的并查集，数据量非常庞大，需要路径压缩。
 #include <stdio.h>
#include <string.h>
int N, T, set[2048], val[2048];
inline int find(int idx)
   {
 static int stk[2048], i;
  for (i = 0; set[idx]; i++) {
stk[i] = idx;
idx = set[idx];
 }
for (i--; i >= 0; i--) {
val[stk[i]] ^= val[set[stk[i]]];
set[stk[i]] = idx;
}
return idx;
 }
int main()
{
int i, j, a, b, t, m, r;
scanf("%d", &T);
for (t = 1; t <= T; t++) {
scanf("%d%d", &N, &m);
memset(set, 0, (N + 1) * 4);
memset(val, 0, (N + 1) * 4);
r = 0;
while (m--) {
scanf("%d%d", &a, &b);
i = find(a);
j = find(b);
if (i == j)
r |= val[a] == val[b];
else {
set[i] = b;
val[i] = !val[a];
}
}
printf("Scenario #%d:\n%s\n\n",
t,
r ? "Suspicious bugs found!" : "No suspicious bugs found!"
);
}
return 0;
}
|