题目分析

本题可以使用带边权的并查集进行求解
我们将所给数据中凡是没有归入同一集合的x、y一律归入同一集合
并利用他们到根节点的距离关系来判断他们的关系，共可分为三类，即：

到根节点距离%3后为1的结点：

表示能够吃掉根节点所代表的动物类型；

到根节点距离%3后为2的结点：

表示能够被根节点所代表的动物类型吃掉的动物类型，由于一共只有三种动物，因此该类型动物也就能够吃掉到根节点距离%3后为1的结点所代表的动物类型

到根节点距离%3后为0的结点：

与根节点所代表的动物属于统一动物类型，也就是代表着根节点所属的动物类型

两个相关数组定义

father[]记录下每个节点的父节点
dp[]记录下每个节点到父节点的距离

在寻找某个结点的根节点的同时完成路径压缩,此时该结点的父节点就是根节点,dp[N]记录下的就是到根节点距离

int getfather(int x){
    if(x!=father[x]){
        int u=getfather(father[x]);
        dp[x]+=dp[father[x]];
        father[x]=u;
    }
    return father[x];
}

第一种说法不成立的情况

1、x或y比n大；
2、在给出该说法之前已经给出了x与y的关系定义且与该说法矛盾
由于我们规定凡是遇到没有归入同一集合的x、y就一律归入同一集合,因此既然此前给出了x与y的定义就说明x与y已经归入同一集合，与当前说法矛盾就说明dp[x]%3与dp[y]%3的结果不一致；

第二种说法不成立的情况

1、x或y比n大；
2、在给出该说法之前已经给出了x与y的关系定义且与该说法矛盾
由于我们规定凡是遇到没有归入同一集合的x、y就一律归入同一集合,因此既然此前给出了x与y的定义就说明x与y已经归入同一集合，与当前说法矛盾就说明dp[x]%3-dp[y]%3不等于1；

将遇到的没有归入同一集合的x、y归入同一集合

对于第一类说法下遇到的没有归入同一集合的x、y

要保证归入统一集合后x、y属于同一类
即若是将x归入y所在的集合 则(dp[x]+dp[fx]-dp[y])%3=0

 fx=getfather[x];
 fy=getfather[y];
 father[fx]=fy;
 dp[fx]=dp[y]-dp[x]; //保证x与y属于一类,即(dp[x]+dp[fx]-dp[y])%3=0

对于第二类说法下遇到的没有归入同一集合的x、y

要保证归入统一集合后x、y满足x吃y
即若是将x归入y所在的集合 则(dp[x]+dp[fx]-dp[y]-1)%3=0

 fx=getfather[x];
 fy=getfather[y];
 father[fx]=fy;
 dp[fx]=dp[y]+1-dp[x]; //保证x与y满足x吃y,即(dp[x]+dp[fx]-dp[y]-1)%3=0

相关代码实现

#include<bits/stdc++.h>
using namespace std;

const int N=50010;
int father[N];
int dp[N]; //记录到父节点的距离

//在寻找根节点的同时完成了路径压缩,此时父节点就是根节点,dp[N]记录下到根节点距离的计算
int getfather(int x){
    if(x!=father[x]){
        int u=getfather(father[x]);
        dp[x]+=dp[father[x]];
        father[x]=u;
    }
    return father[x];
}

int main(){
    int n,k;
    cin>>n>>k;

    for(int i=0;i<n;i++){
        father[i]=i;
        dp[i]=0;
    }

    int res=0;

    for(int i=0;i<k;i++){
        int d,x,y;
        cin>>d>>x>>y;

        if(x>n||y>n){
            res++;
            continue;
        }

        if(d==1){  //当且仅当此前已经将x与y放入同一集合且x与y不属于同一类时才会判为错误
            int fx=getfather(x);
            int fy=getfather(y);

            if(fx==fy&&(dp[x]-dp[y])%3!=0){
                res++;
            }

            else if(fx!=fy){ //当给出的x与y不在同一集合时就说明此前未对x与y的关系做出定义,将其归入同一集合，并认为x与y为同类
                father[fx]=fy;
                dp[fx]=dp[y]-dp[x]; //保证x与y属于一类(即dp[x]+dp[fx]-dp[y])%3=0)
            }
        }


        else{ //当且仅当此前已经将x与y放入同一集合且x与y不满足x吃y时才会判为错误
            int fx=getfather(x);
            int fy=getfather(y);

            if(fx==fy&&(dp[x]-dp[y]-1)%3!=0){
                res++;
            }

            else if(fx!=fy){ //当给出的x与y不在同一集合时就说明此前未对x与y的关系做出定义,将其归入同一集合，并认为x吃y
                father[fx]=fy;
                dp[fx]=dp[y]+1-dp[x]; //保证x与y之间关系满足x吃y(即dp[x]+dp[fx]-dp[y]-1)%3=0)
            }
        }
    }
    cout<<res<<endl;
    return 0;
}