【题解】食物链

题目链接: 食物链

题意:

有三种共N只动物，它们之间只有两种关系：吃与被吃。给定K句话描述两种动物的关系，只要任意一句话满足三种条件之一就是假话，否则为真。问有多少假话。

思路：

1. 首先明确一点，由于我们是逐条看每句话，很多时候我们无法确定所有动物的相互关系，那么 如何处理动物之间的关系 ？
2. 对于无法确定关系的动物，我们可以先将其放到不同集合，而 所有关系确定的动物放到同一集合 。
3. 所有动物的关系与其到根节点的距离相关联 ，而通过记录其与根节点的关系，我们就可以得知所有动物两辆之间的关系。
4. 例如：如果两个点到根节点的距离模3余数相同，则同种动物。否则0被1吃，1被2吃，2被0吃。
5. 注意， 距离可以是负的 ，因为我们只需要知道每个结点到根节点的距离模3余数就可以确定与根节点的关系。这就要求我们计算距离时要写为 (d[x] - d[y]) % 3 这种差的形式。
6. 文中被注释掉的find函数是我开始写错的一个，查清原因后感觉对自己收获很大，放出来希望可以帮助大家更好的理解这道题目。

ps:

错误的find函数以及为什么错:

int find(int x)
{
    if(p[x]==x) return x;
    //错误的点在于没有明确d[x]的作用。
    //d[x]表示x到自己父节点的距离（我们通常会说d[x]是x到祖宗结点的距离，但实际上是x到p[x]指向结点的距离，
    //因为执行完一次find函数p[x]就指向了x的祖宗结点，所以d[x]也就被优化为了x到自己祖宗结点的距离）
    //通过路径压缩的作用，我们执行完find函数后p[x]已经指向了x的祖宗结点，
    //那么此时的d[x]就应该是x到自己祖宗结点的距离，但是我们还没有优化d[px]，d[px]此时只是px到自己父节点的距离，
    //不一定是祖宗结点，所以d[x]就会出错。
    //根本原因就是需要先递归优化d[px]的距离，再回溯优化d[x]的值
    d[x]+=d[p[x]];
    return p[x]=find(p[x]);
}

代码:

#include<iostream>

using namespace std;
const int N=5e4+10;

int p[N],d[N]={0};
int n,m;

int find(int x)
{
    if(p[x]!=x)
    {
        //如果先执行p[x]=find(x),那么p[x]的值就被修改，d[p[x]]就不准了
        int t=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=t;
    }
    //此时p[x]已经指向祖宗结点，所以返回p[x]
    return p[x]; 
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i) p[i]=i;
        
    int ans=0;
    while(m--)
    {
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        
        if(x>n||y>n)ans++;
        else if(t==1)
        {
            //在使用find函数前提前将其记录下来很重要，因为每次调用find函数都有可能不经意间修改p数组和d数组
            int px=find(x),py=find(y);
            
            //如果两者在同一集合，并且到根节点的距离模3余数不同，则不属同一类
            if(px==py&&(d[x]-d[y])%3) ans++;//注意，在操作的时候很容易出现负数，所以要写为(d[x]-d[y])%3!=0的形式
            else if(px!=py)//如果不在同一集合我们将其合并
            {
                p[px]=py;//让x的根节点指向y的根节点
                //(d[x]+?)%3==d[y]%3 --> (d[x]-d[y]+?)%3==0
                d[px]=d[y]-d[x];
            }
        }            
        else 
        {
            int px=find(x),py=find(y);
            
            //x吃y，那么等价于1吃0,2吃1，0吃2。模3余数均差1
            if(px==py&&(d[x]-d[y]-1)%3||x==y) ans++;//同上，因为负数的存在，需要写为差的形式
            else if(px!=py)
            {
                p[px]=py;
                //(d[x]+?)%3==(d[y]+1)%3 --> (d[x]+?-d[y]-1)%3==0
                d[px]=d[y]-d[x]+1;
            }
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}