对于i 创造 i+n 表示一个属于被i吃的种族的元素

创造 i+2n 表示一个属于能吃i的种族的元素

然后裸并查集

#include<iostream>

#include<cstdio>

using namespace std;

int n,k,f[150005],ans;

int find(int i)

{

if (f[i]==i) return i;

else return f[i]=find(f[i]);

}

void merge(int i,int j)

{

int fi=find(i),fj=find(j);

f[fi]=fj;

}

int main()

{

scanf("%d%d",&n,&k);

for (int q=1;q<=n*3+3;q++) f[q]=q;

for (int q=0,e,i,j;q<k;q++)

{

scanf("%d%d%d",&e,&i,&j);

if ((i<1 || j<1 || i>n || j>n)||(e==2 && i==j))

{

ans++;

continue;

}

if (e==1)

{

if (find(i)==find(j+n)||find(i)==find(j+(n<<1)))

{

ans++;

continue;

}

merge(i,j);

merge(i+n,j+n);

merge(i+(n<<1),j+(n<<1));

}

else {

if (find(i)==find(j)||find(i)==find(j+n))

{

ans++;

continue;

}

merge(i,j+(n<<1));

merge(i+n,j);

merge(i+(n<<1),j+n);

}

}

printf("%d",ans);

return 0;

}