洛谷 P2024 [NOI2001]食物鍊 并查集變形 讀入優化

題目連結：

https://www.luogu.com.cn/problem/P2024

參考部落格：

https://www.luogu.com.cn/blog/DanKuroto/solution-p2024

這個部落格真心太牛逼了，講的清晰透徹，真心棒，建議複習時一定要看

算法：

并查集

思路：

1：就是用3倍的并查積的存各種動物的關系，一倍存本身，二倍存獵物，三倍存天敵，特别特别注意：一的獵物的獵物 就是一的天敵

2：每次維護三個并查積的關系

#include <bits/stdc++.h>

using namespace std;
const int maxn=3e5+3;
int fa[maxn],n,k,ans,x,y,z;

inline int read()//讀入優化
{
    int sum=0;
    char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=getchar();
    return sum;
}

int  find(int x)//查根
{
    if(x!=fa[x])fa[x]=find(fa[x]);
    return fa[x];
}

void unity(int x,int y)//合并
{
    int r1=find(fa[x]),r2=find(fa[y]);
    fa[r1]=r2;
}

int main()
{
    ios::sync_with_stdio(0);
    n=read(),k=read();
    for(int i=1;i<=3*n;i++)fa[i]=i;//對于每種生物：設 x 為本身，x+n 為獵物，x+2*n 為天敵
    for(int i=1;i<=k;i++)
    {
        z=read(),x=read(),y=read();
        if(x>n||y>n){   ans++;continue;}// 不屬于該食物鍊顯然為假
        if(z==1)
        {
            if(find(x+n)==find(y)||find(x+2*n)==find(y)){ans++;continue;}
            //如果1是2的天敵或獵物，顯然為謊言
            unity(x,y);unity(x+n,y+n);unity(x+2*n,y+2*n);
            //如果為真，1，2為同類，1的獵物和2的獵物也為同類，1的天敵和2的天敵也為同類
        }
        else if(z==2)
        {
            if(x==y){ans++;continue;}
            if(find(x)==find(y)||find(x+2*n)==find(y)){ans++;continue;}
            //如果1是2的同類或獵物，顯然為謊言，隻有1是2的天敵才正确
            unity(x,y+2*n);unity(x+n,y);unity(x+2*n,y+n);
            //如果為真，那麼1的同類是2的天敵，1的獵物是2的同類，1的天敵是2的獵物
        }
    }
    printf("%d\n",ans);
    return 0;
}