poj 1182 食物链

#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>const int MAX=50005;int father[MAX];int rank[MAX];//初始化集合 void Make_Sent(int x){    father[x]=x;    rank[x]=0;}//查找x的集合，回溯时压缩路径，并修改x与father[x]的关系 int Find_set(int x){    int t;     if(x!=father[x])    {        t = father[x];        father[x]= Find_set(father[x]);        //更新x与father[X]的关系         rank[x] = (rank[x]+rank[t])%3;    }    return father[x];}//合并x,y所在的集合 void Union(int x,int y,int d){    int xf = Find_set(x);    int yf = Find_set(y);    //将集合xf合并到yf集合上     father[xf] = yf;    //更新 xf 与father[xf]的关系     rank[xf]=(rank[y]-rank[x]+3+d)%3;}int main(){    int totle=0;    int i,n,k,x,y,d,xf,yf;    scanf("%d%d",&n,&k);    for(i=1;i<=n;++i)Make_Sent(i);    while(k--)    {        scanf("%d%d%d",&d,&x,&y);        //如果x或y比n大，或x吃x，是假话         if(x>n||y>n||(d==2 && x == y))        { totle++;   }        else        { xf = Find_set(x); yf = Find_set(y); //如果x，f的父节点相同 ，那么可以判断给出的关系是否正确的  if(xf == yf) {     if((rank[x]-rank[y]+3)%3 != d-1)         totle++;         } else {     //否则合并x，y      Union(x,y,d-1); }        }    }    printf("%dn",totle);return 0;}