显而易见，此题是道并查集的题，但与以往的并查集应用不同的是，这个是带权的，而带的权就是权两边端点的关系，这个关系要满足传递性。而划分集合的依据是，集合中的点可以确定这个关系。对于常用的并查集的应用的话，这个关系指的就是属于。

    而这道题就是不断的维护一个保持这样关系的数据结构集合，如果当前要添加进来的某个关系与集合中的结构发生冲突，就是假话了。难点在于合并时的关系维护（直接修改合并过来集合的根节点的关系就可以），其次是路径压缩的时候，对于这个操作，在回朔的时候，当之前的父节点操作完，说明父节点已经接到这个集合的根节点下，这个父节点的关系也已经确定了，对于当前节点，先不压缩过去，先根据父节点的关系和当前节点与该节点的关系，推出当前节点的关系后，再压缩过去，这样就完成了，路径压缩时候的关系更新。

(以上是copy大牛的原话，以下是自己的理解)

代码及其注释如下：

void make_set(int n)
{
 int i;
 for(i=0;i<=n;i++)
 {
  root[i] = i;     //root[i]代表着i动物的指向，即如果root[i]=j，那么动物i和动物j间有联系(传递性:如果i和k有联系，则j和k也有联系)
  

  kind[i] = 0;    //kind[i]代表动物i相对于动物root[i]的种类 0表示同类，1表示前者吃后者，2表示后者吃前者
 }
}

int find_set(int x)
{//找到x的根返回，并且压缩路径，将原先离根远的直接放到根上去，递归过程
 

if(x == root[x])
  return x;
 
 int t = root[x];
 root[x] = find_set(t);//递归调用

 kind[x] = (kind[x] + kind[t]) % 3;//相对论（超赞）的应用，kind[i]的定义是i相对于root[i]的种类，由传递性得出此式（出自一位大牛）
 

 return root[x];
}

void unionx(int a, int b, int relation)
{ 
 root[x] = y;  //x指向y，修改kind[x]
 kind[x] = relation % 3;
}

d=1时，种类应该相同: kind[x] == kind[y];

x和y的关系是( (d-1) + kind[fy]+ (3-kind[fx]) )%3;