|
|
思路： 這題的背景是亮點，描述如下： 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;
}
|