题解 | #食物链#

通过并查集 开辟三倍空间来分别表示 亲戚 天敌 食物 三种关系 详细看代码注释

```#include<bits/stdc++.h>
using namespace std;
const int N=50010;
long long cnt=0;
int p[3*N];

//查找亲戚
int find(int x){
    if(p[x]!=x){
        p[x]=find(p[x]);
    }
    return p[x];
}
//合并
void merger(int x,int y){
    int x1=find(x);
    int y1=find(y);
    p[x1]=y1;
}

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=3*n;i++){
      p[i]=i;
    }
    int cnt=0;            //谎话数
    for(int i=0;i<k;i++){
        int op,x,y;    
        cin>>op>>x>>y;
        if(x>n || y>n)                                
            cnt++;
        else if(op==1){
            if(find(x+n)==find(y) || find(y+n)==find(x)){ //互为食物关系 谎话
                cnt++;
            }else{
                //找亲戚
                merger(x,y);
                merger(x+n,y+n);
                merger(x+2*n,y+2*n);
            }
        }else if(op==2){
            if(x==y || find(x)==find(y) || find(y)==find(x+n)){ //相同 亲戚 y吃x 谎话
                cnt++;
            }else{
                //x+n是x的天敌
                //x+2n是x+n的天敌
                //x是x+2n的天敌
                merger(x,y+n);
                merger(x+n,y+2*n);
                merger(x+2*n,y);
            } 
        }
    }
    cout<<cnt<<endl;
    return 0;
}