POJ1182(食物链)

链接：https://vjudge.net/problem/POJ-1182
思路：由于已经确定了只有三种关系并且为一个圈，我们如果x->y为0表示同类，x->y为1表示x吃y，x->y为2表示y吃x，那么整个关系可以用模3的加法来传递下去，也就是说我们记录某个点到根节点的关系，合并的时候沿途记录到根节点距离模3的值，即可维护与根节点的关系。如果二者根节点不同，那么他们之前一定没有进行过任何相关的操作，此时正常维护二者的关系。否则判断二者关系是否有误即可。（关系并查集和带权并查集合并时关键需要画出矢量图，总是跟矢量密切相关，矢量图画对了关系就有了）
代码：

#include<cstdio>
using namespace std;

int n,k;
const int maxn = 50010;
int par[maxn];
int rel[maxn];

int getroot(int a){
    if(par[a]==a)return a;
    int px = par[a];
    par[a] = getroot(par[a]);
    rel[a] = (rel[a]+rel[px]+3)%3;
    return par[a];
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<=n;i++){
        par[i] = i;
        rel[i] = 0;
    }
    int res = 0;
    for(int i=0;i<k;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int p1 = getroot(b);
        int p2 = getroot(c);
        if(b>n||c>n){
            res++;
            continue;
        }
        if(a==2&&b==c){
            res++;
            continue;
        }
        if(p1!=p2){
            par[p2] = p1;
            rel[p2] = (3+a-1+rel[b]-rel[c])%3;
        }
        else{
            if(a==1&&rel[b]!=rel[c]){
                res++;
                continue;
            }
            if(a==2&&((3-rel[b]+rel[c])%3)!=a-1){
                res++;
                continue;
            }
        }
    }
    printf("%d\n",res);
    return 0;
}