这个题自从a了上面那道题之后就变得蛮水的。但是它的合并着实让我郁闷了一番。
考虑维护这样一个并查集：
fa纪录它的父亲节点，up纪录它到根节点的距离。
那么根据每个节点mod 3的值，就可知道是那种动物。（换句话说，mod 3相同的动物，是一种动物……）
那么对于询问1
如果在同一个集合里，就计算它们的up mod 3 的值，如果相同就是真话。
如果不在同一个集合里，那这就默认是真话，把它俩合并。要跟据up的值算出根节点的关系，然后更新根节点的up值。
对于询问2，
如果在同一个集合里，计算mod 3 值，如果一个等于另一个加一，或者一个是2另一个是0（环的情况），那么就是真话。
如果不在同一个集合里，那也默认真话，把他俩合并。更新根节点up值。
详见代码：
View Code var f:boolean; n,k,fal,z,x,y,i:longint; up:array[1..50000] of longint; fa:array[1..50000] of longint;procedure init;var i:longint;beginfor i:=1 to n dobegin fa[i]:=0; up[i]:=0;end;end;function find(x:longint):longint;beginif fa[x]=0 then exit(x); find:=find(fa[x]); up[x]:=up[x]+up[fa[x]]; fa[x]:=find;end;procedure work2(x,y:longint);var l,r,p,q:longint;beginif (x>n) or (y>n) then begin fal:=fal+1; exit;end;if x=y then begin fal:=fal+1; exit;end; q:=find(x); p:=find(y);if p<>q then begin l:=up[x] mod 3+1; r:=up[y] mod 3; fa[p]:=q;if r<=l then up[p]:=up[q]+(l-r) else up[p]:=up[q]+3-(r-l);end else begin l:=(up[x]) mod 3; r:=(up[y]) mod 3;if l+1=r then f:=true else if (l=2) and (r=0) then f:=true else inc(fal);end;end;procedure work1(x,y:longint);var l,r,p,q:longint;beginif (x>n) or (y>n) then begin fal:=fal+1; exit; end;if x=y then exit; q:=find(x); p:=find(y);if p<>q then beginif up[x]>up[y] then begin fa[p]:=q; up[p]:=up[q]+(up[x]-up[y]) mod 3;end else begin fa[q]:=p; up[q]:=up[p]+(up[y]-up[x]) mod 3;end;end else begin l:=(up[x]) mod 3; r:=(up[y]) mod 3;if (l<>r) then fal:=fal+1; end;end;begin readln(n,k); fal:=0; init;for i:=1 to k dobegin readln(z,x,y);if z=2 then work2(x,y) else work1(x,y);end; writeln(fal);end.转载于:https://www.cnblogs.com/zjerly/archive/2011/10/28/2227229.html
相关资源：JAVA上百实例源码以及开源项目