题解 P2024 【食物链】

· · 题解

用并查集来做所以想到了代码就不困难

最核心的就是要存三倍分别代表Ni是哪个种类，然后每个并查集里的话同时成立或不成立

还有就是注意特判一些比如超出N范围的信息肯定是假的 直接

ans++ 下面看代码吧

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int f[150010],n,T,k,x,y,fx,fy,ans=0;
int getf(int x){
    if(x==f[x]) return f[x];
    f[x]=getf(f[x]);
    return f[x]; 
}
void merge(int a,int b){
    f[a]=getf(b);
}
int main(){
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n*3;i++) f[i]=i;
    while(T--){
        scanf("%d%d%d",&k,&x,&y);
        if(x>n||y>n){
            ans++; continue;
        }
        fx=getf(x),fy=getf(y);
        if(k==1){
            if(fx==fy) continue;
            if(fx==getf(x+n)||fx==getf(x+n+n)||fy==getf(x+n)||fy==getf(x+n+n)){
                ans++; continue;
            }
            merge(fx,fy); merge(getf(x+n),y+n); merge(getf(x+n+n),y+n+n);
        }
        if(k==2){
            if(x==y){
                ans++; continue;
            }
            if(fx==fy||getf(x+n)==fy||getf(x+n+n)==getf(y+n)||fx==getf(y+n+n)){
                ans++; continue;
            }
            merge(fx,y+n); merge(getf(x+n),y+n+n); merge(getf(x+n+n),fy);
        }
    }
    printf("%d",ans);
    return 0;
}