食物链

拆点；一个点i可能的种类为A，B,C
将一个点i拆成三个点，相当于三种情况；
i表示A，i+n表示B,i+n+n表示C

#include<bits/stdc++.h>
using namespace std;
#define int long long
int fa[151000],k,n;
int find(int x)
{
    return fa[x]==x ? x:fa[x]=find(fa[x]);
}
int merge(int a,int b)
{
    fa[find(a)]=find(b);
    return 0;
}
signed main()
{
    cin>>n>>k;
    int cnt=0;
    for(int i=1;i<=3*n;i++) fa[i]=i;
    for(int i=1;i<=k;i++)
    {
        int d,x,y;
        cin>>d>>x>>y;
        if(x>n||y>n) {cnt++;continue;}
        if(d==1)
        {
            if(find(x)==find(y+n)||find(x)==find(y+2*n)){
                cnt++;continue;
            }
            merge(x,y);//如果x与y同类，x的每个情况都与y的每个情况在同一个集合；
            merge(x+n,y+n);
            merge(x+n+n,y+n+n);
        }
        else{
            if(find(x)==find(y)||find(x)==find(y+2*n)){
                cnt++;continue;
            }
            merge(x,y+n);//x吃y,则可能的情况AB、BC、CA；
            merge(x+n,y+2*n);
            merge(x+2*n,y);
        }
    }
    cout<<cnt;
    return 0;
}