食物链是一道经典的并查集题，这道题难在怎么确定两个动物之间的关系。

看了罗德安大神的分析，有种豁然开朗的感觉。

问题分析：

    我们把已经确立了关系的动物分到一个群落里，对于每一个提到的两个数字编号， 看它们是

否属于同一个群落，如果是的那么根据它们已有的关系，我们作出相应的判断 即可；若它们属于

不同的群落，那么根据互相的关系将两个群落合并；若恰有一个没有 加入到任意一个群落之中，

那么将这一个并入另一个的群中即可；若两个都未加入任意 群中，那么我们新建一个群即可。

基本思路：

这一题的难点在于记录动物之间的关系，即ABC三种动物是循环被吃的，我们用 0，1，2表示，记录

在rank[i]中，如果i吃j，则让rank[i]=(rank[j]+1)%3.为了便于处理， rank[i]表示第i个动物相对

于其父节点动物的差值，而不直接表示他本身的类别。这样 我们可以通过并查集自身的性质巧妙的

维护rank[]的值，所有根结点的rank[]值为0.

/*Accepted    512K    329MS    C++    1029B    2012-08-08 15:23:35*/#include
      
       #include
       
        #include
        
         const int MAXN = 50050;int p[MAXN], rank[MAXN];int n, k, op, ans;int find_set(int x){    int t = p[x];    if(p[x] != x)        p[x] = find_set(p[x]);    rank[x] = (rank[x] + rank[t]) % 3;    return p[x];}void union_set(int x, int y, int op){    int nx = find_set(x);    int ny = find_set(y);    p[nx] = ny;    rank[nx] = (rank[y] - rank[x] + 3 + op - 1) % 3;}int judge(int x, int y, int op){    if(find_set(x) == find_set(y))    {        if(rank[x] != (rank[y] + op - 1) % 3 )            return 1;    }    return 0;}int main(){    int i, x, y;    scanf("%d%d", &n, &k);    ans = 0;    for(i = 1; i <= n; i ++)    {        p[i] = i;        rank[i] = 0;    }    while(k --)    {        scanf("%d%d%d", &op, &x, &y);        if(x > n || y > n || judge(x, y, op))            ++ ans;        else            union_set(x, y, op);    }    printf("%d\n", ans);    return 0;}