食物链

建图种类并查集即可

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int fa[N],d[N];
int ask(int x)
{
    if(fa[x]!=x)
    {
        int root=ask(fa[x]);
        d[x]+=d[fa[x]];
        fa[x]=root;
    }
    return fa[x];
}

int main()
{
    for(int i=1;i<=N-5;i++) fa[i]=i;
    int n,T;
    cin>>n>>T;
    int res=0;
    while(T--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(c>n||b>n||(a==2&&b==c))  {res++; continue;}
        int pa=ask(b);
        int pb=ask(c);
        if(a==1)//b c同类
        {
            if(pa==pb)//假如关系确认
            {
                if((d[b]-d[c])%3!=0)    res++;
            }
            else//建立关系
            {
                fa[pa]=pb;
                d[pa]=d[c]-d[b];
            }
        }
        else//b 吃 c
        {
            if(pa==pb)//假如关系确认
            {
                if((d[b]-d[c]-1)%3!=0)    res++;
            }
            else//建立关系
            {
                fa[pa]=pb;
                d[pa]=d[c]-d[b]+1;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}
/*
我们按权值并查集定义三类.
x%3==0表示与根同类
x%3==1表示可以吃根节点
x%3==2表示可以被根节点吃
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
*/