给定一个对称的二元关系(symmetric)R，关系中的每个元素有一个权值函数V.
若对于任意的
(a,b) in R
(b,c) in R
如果存在一个函数F，使得V(a,c)=F[V(a,b),V(b,c)]
则称该关系传递可推导。

该题显然满足以上条件。
对于A吃B 则V((A,B))=1 V((B,A))=-1
对于A和B同类 则V((A,B))=0 V((B,A))=0
F[V1,V2]=(V1+V2)%3推出

也就是说，对于已知关系的传递闭包，我们都能推导出来。
既然能推导出传递闭包，所以维护一棵树就够了……

• Re:向量根本没有命中要害，我以为，不如说是用并查集维护一个传递可推导关系…… (312) forgetEver 2012-09-30 13:10:09
• Re:赞！这个说法比较靠谱~这种并查集题的关键是公式，公式就是已知传递可推导关系找出实例化的代数表达和运算符~ (2) openthedoor 2013-09-12 13:21:39