食物链 – POJ1182

题意：A 国有３个物种，A 捕食 B，B 捕食 C，C 捕食 A．某人对 A 国的 n 个动物发表评价，内容如下：
1 x y : x 和 y 是一个物种
2 x y : x 捕食 y
如果这个人的某个评论与前文的真话出现矛盾或x,y>n，这个评论成为假话，反之成为真话．
求他说了多少假话．

分析：由于捕食关系成环，如果我们发现了一条食物链A->B->C->D->E->F…，那么一定有 A=D,B=E,C=F，以此类推．也就是说食物链上每３个动物都是不同的，隔着两个的动物是相同的．(显然)，因此我们可以记录每只动物距所在食物链最前端的距离．这个就可以使用并查集完成．
如果我们发现了这样的两条食物链：
A->B
D->E
且某人说 B 和 E 是同一个物种，按照定义，这是句真话．因此我们需要将两个食物链合并．
合并连边A->D，为了保证 B 和 E 仍然是一个物种，D 距离 A 的距离应该设为 0．保证了食物链的合法性．

补充：网络上普遍的做法是保存节点与父节点的吃与被吃的关系，但这种关系不好想，也不容易推广到物种更多的食物链上去．这篇博客的做法，我自认为是基于同余的 easy but effective 的做法．

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 50001

using namespace std;

int fa[MX],sp[MX],n,k;

int findfa(int x)
{
    if(x==fa[x])return x;
    else
    {
        findfa(fa[x]);
        sp[x]+=sp[fa[x]];
        fa[x]=fa[fa[x]];
        return fa[x];
    }
}

inline int same(int a,int b)
{
    int f1=findfa(a),f2=findfa(b);
    if(f1==f2)
    {
        if(sp[a]%3==sp[b]%3)return 0;
        else return 1;
    }
    else
    {
        fa[f1]=f2;
        sp[f1]=(sp[b]-sp[a])%3+3;
        return 0;
    }
}

inline int eat(int a,int food)
{
    int f1=findfa(a),f2=findfa(food);
    if(f1==f2)
    {
        if(sp[a]%3==(sp[food]+1)%3)return 0;
        else return 1;
    }
    else
    {
        fa[f1]=f2;
        sp[f1]=(sp[food]-sp[a])%3+4;
        return 0;
    }
}

int main()
{
    int a,b,c,ans=0;
    scanf("%d%d",&n,&k);
    for(int i=0;i<=n;i++)fa[i]=i;
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(b>n||c>n)ans++;
        else if(a==1)ans+=same(b,c);
        else ans+=eat(b,c);
    }
    printf("%d\n",ans);
    return 0;
}