食物链

食物链

因为不知道要输入的 x ，是属于A，B，C，哪个位置上的，所以把空间开了三倍，每一种状态都保存一下

如果 x 与 y 同类，那么judge(x,y)为true。

如果 x 吃 y 那么，judge(x,y+n)为true

这个题卡的点在于，poj会卡cin，所以应该用scanf()进行读入

代码：

// Created by CAD on 2020/1/15.
#include <cstdio>
using namespace std;

const int maxn=5e4+5;
int f[3*maxn];
inline int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
inline bool judge(int x,int y)
{
    return find(x)==find(y);
}
inline void merge(int x,int y)
{
    x=find(x),y=find(y);
    f[x]=y;
}
int main()
{
    int n,k;    scanf("%d%d",&n,&k);
    int ans=0;
    for(int i=1;i<=3*n;++i)
        f[i]=i;
    for(int i=1;i<=k;++i)
    {
        int d,x,y;
        scanf("%d%d%d",&d,&x,&y);
        if(x<1||x>n||y<1||y>n) ans++;
        else{
            if(d==1)
            {
                if(judge(x,y+n)||judge(x,y+2*n))
                    ans++;
                else{
                    merge(x,y);
                    merge(x+n,y+n);
                    merge(x+2*n,y+2*n);
                }
            }
            else {
                if(judge(x,y)||judge(x,y+2*n))
                    ans++;
                else{
                    merge(x,y+n);
                    merge(x+n,y+2*n);
                    merge(x+2*n,y);
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}