解题思路

数据结构设计

采用三倍节点扩展的并查集结构：

• 每个动物对应三个节点：n、2n、3n
• 使用并查集维护这3n个节点的连通关系

关系定义规则

1. 同类关系判定条件

1. 若a和b都捕食同一动物c，则a与b为同类
2. 若存在食物链a→c→d→b，则a与b为同类

2. 并查集操作规则

关系验证方法

• 同类验证：检查a_n与b_n是否连通（根节点相同）
• 捕食验证：
  • a捕食b → 检查a_n与b_2n是否连通
  • b捕食a → 检查b_n与a_2n是否连通

实现步骤

1. 初始化3n大小的并查集
2. 对每个关系声明：
   • 若声明同类关系，执行同类连接操作
   • 若声明捕食关系，执行捕食连接操作
3. 每次操作前进行关系验证，排除矛盾声明

///并查集
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int maxn=50005;
int fa[maxn*3];
int n,m;
int ans;

int Find(int x){
    int t=x;
    while(fa[t]!=t) t=fa[t];
    while(x!=t)
    {
        int temp=fa[x];
        fa[x]=t;
        x=temp;
    }
    return t;
}

void Join(int x,int y){
    int fx=Find(x),fy=Find(y);
    if(fx!=fy)
        fa[fx]=fy;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=3*n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int num,a,b;
        scanf("%d%d%d",&num,&a,&b);
        if(a<1||a>n||b<1||b>n) {
            ans++; continue;
        }
        if(num==2&&a==b){
            ans++;continue;
        }
        if(num==1){//a,b同类
            if(Find(a)==Find(b+n)||Find(b)==Find(a+n)) ans++;//如果a吃b或者b吃a，说明是假话
            else {//否则是真话，建立a和b同类的关系
                Join(a,b);
                Join(a+n,b+n);
                Join(a+2*n,b+2*n);
            }
        }
        else if(num==2){//a吃b
            if(Find(a)==Find(b)||Find(b)==Find(a+n)) ans++;//如果a,b同类或者b吃a，说明是假话
            else {//否则是真话，建立a吃b的关系
                Join(a,b+n);
                Join(a+n,b+2*n);
                Join(a+2*n,b);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}