【问题描述】

  Hopper教授正在研究一种罕见的臭虫性行为。

.他假定它们有两个不同的性别，他们只会与异性XXOO。

.在他的实验，个别的臭虫和它们之间的交配行为是很容易识别，因为他们的背上印有号码。. 

给出一系列臭虫的交配行为名单，判断实验结果是否支持他的“臭虫之间没有同性恋的假设”。

【解题报告】

  和NOIP2010的监狱差不多，两个并查集解决问题。

 

1 program bugs;  2 var  3   k,nn,i,n,m,x,y,x0,y0:longint;  4   a,b,c:array[0..1000001]of longint;  5   father:array[0..40001]of longint;  6   can:boolean;  7  8 procedure init;  9 begin 10   assign(input,'bugs.in'); 11   reset(input); 12   assign(output,'bugs.out'); 13   rewrite(output); 14 end; 15 16 procedure outit; 17 begin 18   close(input); 19   close(output); 20 end; 21 22 function find(x:longint):longint; 23 begin 24   if father[x]=x then exit(x); 25   father[x]:=find(father[x]); 26   exit(father[x]); 27 end; 28 29 procedure main; 30 begin 31   readln(nn); 32   for k:=1 to nn do 33   begin 34     writeln('Scenario #',k,':'); 35     can:=false; 36     readln(n,m); 37     for i:=1 to m do readln(a[i],b[i]); 38     for i:=1 to 2*n do father[i]:=i; 39     for i:=1 to m do 40     begin 41       x:=find(a[i]); y:=find(b[i]); 42       x0:=find(a[i]+n); y0:=find(b[i]+n); 43       if (x=y)or(x0=y0) then 44       begin 45         can:=true; 46         writeln('Suspicious bugs found!'); 47         writeln; 48         break; 49       end; 50       if x<>y0 then father[x]:=y0; 51       if y<>x0 then father[y]:=x0; 52     end; 53     if can then continue; 54     writeln('No suspicious bugs found!'); 55     writeln; 56   end; 57 end; 58 59 begin 60   init; 61   main; 62   outit; 63 end.