> 我的理解是，对于集合里的任意两个元素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有所帮助 :]

• Re:总结此题可以精简到一个并查集！并且用向量的思考模式想整个过程相当简单！ (9) skyhacker 2010-12-07 13:36:54