http://poj.org/showmessage?message_id=152847 我的理解是，对于集合里的任意两个元素a,b而言，它们之间必定存在着某种联系，> > 因为并查集中的元素均是有联系的，否则也不会被合并到当前集合中。那么我们> > 就把这2个元素之间的关系量转化为一个偏移量，以食物链的关系而言，不妨假设> > a->b 偏移量0时 a和b同类> > a->b 偏移量1时 a吃b> > a->b 偏移量2时 a被b吃，也就是b吃a> > 有了这些基础，我们就可以在并查集中完成任意两个元素之间的关系转换了。> > 不妨继续假设，a的当前集合根节点aa，b的当前集合根节点bb，a->b的偏移值为d-1（题中给出的询问已知条件）> > (1)如果aa和bb不相同，那么我们把bb合并到aa上，并且更新delta[bb]值（delta[i]表示i的当前集合根节点到i的偏移量）> >     此时 aa->bb = aa->a + a->b + b->bb，可能这一步就是所谓向量思维模式吧> >     上式进一步转化为：aa->bb = (delta[a]+d-1+3-delta[b])%3 = delta[bb]，（模3是保证偏移量取值始终在[0,2]间）> > (2)如果aa和bb相同，那么我们就验证a->b之间的偏移量是否与题中给出的d-1一致> >     此时 a->b = a->aa + aa->b = a->aa + bb->b，> >     上式进一步转化为：a->b = (3-delta[a]+delta[b])%3，> >     若一致则为真，否则为假。> > 希望可以对LS有所帮助 :]

pre[x]：表示x的父节点为pre[x]p=find(x),其中p表示x的根节点relation[x] :表示节点x与其根节点的关系，             relation[x]=p->x(因为后面要用到向量，所以先把向量的方向说明出来，relation[x]向量代表从根节点p指向x的向量)             relation[x]=0 表示p与x同类             relation[x]=1 表示p吃x			 relation[x]=2 表示x吃p ----------------------------------------------------------------------------------- 对于给定的一句话 d,x,y 先判断x,y是否在同一个集合关系(集合是按照能够判断x,y关系来划分的) if(x,y在同一个集合) { 	判断说的这句话的真假 ; }  else { 	这句话认为为真，将x,y合并起来; }-----------------------------------------------------------------------------------  判断一句话的 真假可以有两种办法 (方法一)直接列出所有为真的情况，如果这句话不符合列举出的所有情况，则这句话为假 1) d==1 表示x,y为同类  relation[x]    relation[y]    0               0    1               1    2               2所以如果relation[x]!=relation[y]，则这句话为假话2）d==2 表示x吃yrelation[x]    relation[y]    0               2     //此时x与根节点同类，要让x吃y,relation[y]=2     2               1     //此时x吃根节点，要让x吃y,则y与根节点同类，relation[y]=1     1               0     //此时x被根节点吃，要让x吃y,则y应该吃根节点，relation[y]=1如果不满足这三组对应的 值，则 这句话为假(方法二)详细见 http://poj.org/showmessage?message_id=152847按照向量来做x->y=x->p+p->y//因为此时p=q,所以可以将p换成q    =-relation[x]+relation [y]    =relation[y]-relation[x]//再进一步处理，为了防止为表达式的值为负数，给它加上3，	=(relation[y]-relation[x]+3)%3 // 为使表达式的值在0到2之间，给表达式模 上3又因为题目中给的是 d==1 x,y为同类，对应于我们规定的同类为0，应该将d-1所以判断我们计算出的偏移量和说的那句话的偏移量是否一致，如果不一致，则说的 假话即((relation[y]-relation[x]+3)%3) !=d-1,则这句话为假话---------------------------------------------------------------------------------------   p,q不同时  合并 x,y将q合并到p上，同时更新relation[q] p->q=p->x+x->y+y->q    =relation[x]+(d-1) +(-relation[y])//同样为防止表达式的值为负，加上3     =(relation[x]-relation[y]+(d-1)+3) %3//为了使表达式的值在0到2之间，模上3 即 relation[q]=(relation[x]-relation[y]+(d-1)+3) %3----------------------------------------------------------------------------------------压缩路径的时候，同时更新relation[]数组详细见：http://blog.csdn.net/ditian1027/article/details/20804911现在知道儿子节点x, 父亲节点 fx,爷爷节点ffx,要求ffx->x则 ffx->x=ffx->fx+fx->x         =relation[fx]+relation[x]即 relation[x]=(relation[x]+relation[tmp])%3 将fx记作x的亲生父亲，又因为find()函数是带路径压缩的，经过压缩后，x的父亲节点变为fx‘,不能用来计算 而我们需要的是fx的值 ，所以用tmp将它记录下来，再压缩---------------------------------------------------------------------------------------- 

#include<stdio.h>#define maxn 50010int pre[maxn],relation[maxn];int find(int a){	int tmp;	tmp=pre[a];	if(a!=pre[a])	pre[a]=find(pre[a]);	relation[a]=(relation[a]+relation[tmp])%3;	return pre[a];}void unionroot(int x,int y,int d){	int p,q;	p=find(x);	q=find(y);	pre[q]=p;	relation[q]=(relation[x]-relation[y]+3+d-1)%3;}int main(){	int i,n,k,sum,x,y,p,q,d;	scanf("%d %d",&n,&k);		for(i=0;i<=maxn;i++)		{			pre[i]=i;			relation[i]=0;		}		sum=0;		while(k--)		{			scanf("%d %d %d",&d,&x,&y);			p=find(x);			q=find(y);			if((x>n||y>n)||(x==y&&d==2))			{			sum++;			continue;		    }			if(p==q)			{				if((relation[y]-relation[x]+3)%3!=d-1)					 sum++;			}				else				unionroot(x,y,d);		}		printf("%d\n",sum);}

#include<stdio.h>#define maxn 50010int pre[maxn],relation[maxn];int find(int a){	int tmp;	tmp=pre[a];	if(a!=pre[a])		pre[a]=find(pre[a]);	relation[a]=(relation[a]+relation[tmp])%3;	return pre[a];		}void unionroot(int x,int y,int d){	int p,q;	p=find(x);	q=find(y);	pre[p]=q;	relation[p]=(relation[y]-relation[x]+3+d-1)%3;}int main(){	int i,n,k,sum,x,y,p,q,d;	scanf("%d %d",&n,&k);		for(i=0;i<=maxn;i++)		{			pre[i]=i;			relation[i]=0;		}		sum=0;		while(k--)		{			scanf("%d %d %d",&d,&x,&y);			p=find(x);			q=find(y);			if((x>n||y>n)||(x==y&&d==2))			{			sum++;			continue;		    }				if(p==q)							{				if(d==1&&relation[x]!=relation[y])				++sum;				if(d==2)				{					if(relation[x]==0&&relation[y]!=2)					++sum;					if(relation[x]==1&&relation[y]!=0)					++sum;					if(relation[x]==2&&relation[y]!=1)					++sum;									}															}				else  				unionroot(x,y,d);		}		printf("%d\n",sum);}