题解 | #食物链#

法1：三倍空间，种类并查集

类似于：https://ac.nowcoder.com/acm/problem/16591

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5;

int fa[N];
int n,k;

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

bool check(int op,int x,int y){
    if(x>n||y>n) return true;   
    if(x==y&&op==2) return true;  // x 吃 x 
    if(op==1){   
        if(find(x+n)==find(y)||find(x)==find(y+n))  // x 吃 y 或 y 吃  x  => 假 
        return true;
    }
    else{
        if(find(y+n)==find(x)||find(x)==find(y))   //  y 吃  x  或  x、y 是同类  => 假 
        return true;
    }
    return false;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=3*n;i++) fa[i]=i;   //对 于每种生物：设 x 为本身，x+n 为猎物，x+2*n 为天敌 

    int ans=0;
    for(int i=1;i<=k;i++){
        int op,x,y;
        cin>>op>>x>>y;
        if(check(op,x,y)) ans++;
        else{
            if(op==1){ // x、y 为同类 ，是真话 
                fa[find(x)]=find(y); // x的同类 = y的同类 
                fa[find(x+n)]=find(y+n); // x的猎物 = y的猎物 
                fa[find(x+2*n)]=find(y+2*n); // x的天敌 = y的天敌 
            }
            else{  // x 吃 y ，是真话 
                fa[find(x)]=find(y+2*n);  // x的同类 = y的天敌 
                fa[find(x+n)]=find(y);    // x的猎物 = y的同类 
                fa[find(x+2*n)]=find(y+n);  // x的天敌 = y的猎物 
            } 
        }
    }
    cout<<ans<<endl;
    return 0;
}

法二：带权并查集

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10 ;

struct node{
    int fa;        // p[i].fa：i的父节点
    int relation;  // p[i].relation：i与其父节点的关系
    /*
    relation = 0：i与其父节点为同类
    relation = 1：父节点吃i
    relation = 2：i吃其父节点
    */
}p[N];
int n,k;

int get_mod(int a,int b){  // 防止a为负数
    return (a%b+b)%b;
}

int find(int x){
    if(x==p[x].fa) return x;
    int t=p[x].fa;
    p[x].fa=find(t);
    p[x].relation=(p[x].relation+p[t].relation)%3;
    return p[x].fa;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) p[i].fa=i;  
    int ans=0;
    for(int i=1;i<=k;i++){
        int op,x,y;
        cin>>op>>x>>y;
        if(x>n||y>n||(op==2&&x==y)) ans++;
        else{
            int fx=find(x),fy=find(y);
            if(fx!=fy) p[fx].fa=fy,p[fx].relation=get_mod(op-1+p[y].relation-p[x].relation,3);
            else {
                if(op==1&&p[x].relation!=p[y].relation) ans++;
                else if(op==2&&get_mod(p[x].relation-p[y].relation,3)!=(op-1)) ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}