种类并查集的经典题目，和NOIP2010里的关押罪犯一个类型，0，1，2表示三个种类，在合并时用类似向量的方法去导公式，其他的模拟操作即可。
View Code 1 program pku1182(input,output); 2 var 3 father,r : array[0..50000] of longint; 4 i,n,x,y,answer,k,t : longint; 5 function find(i : longint):longint; 6 var 7 temp:longint; 8 begin 9 if father[i]=i then 10 exit(i); 11 temp:=father[i]; 12 father[i]:=find(father[i]); 13 r[i]:=(r[temp]+r[i]) mod 3; 14 exit(father[i]); 15 end; 16 procedure union(x,y,h:longint); 17 var 18 a,b:longint; 19 begin 20 a:=find(x); 21 b:=find(y); 22 father[a]:=b; 23 r[a]:=(r[y]+h-r[x]+3) mod 3; 24 end; 25 begin 26 answer:=0; 27 readln(n,k); 28 for i:=1 to n do 29 father[i]:=i; 30 for i:=1 to k do 31 begin 32 readln(t,x,y); 33 if (x>n)or(y>n) then 34 begin 35 inc(answer); 36 continue; 37 end; 38 case t of 39 1:if find(x)=find(y) then 40 begin 41 if r[x]<>r[y] then 42 inc(answer) 43 end 44 else 45 union(x,y,0); 46 2:begin 47 if x=y then 48 begin 49 inc(answer); 50 continue; 51 end; 52 if find(x)=find(y) then 53 begin 54 if r[x]<>(r[y]+1) mod 3 then 55 inc(answer) 56 end 57 else 58 union(x,y,1); 59 end; 60 end; 61 end; 62 writeln(answer); 63 end.