find函数中len[x]的具变化情况？

Question

#include<iostream>
using namespace std;
const int N=5e4+10;
int animal[N],len[N];//length[x]是x到根节点的距离
int quantity;//假话的数量
int find(int x)//路径压缩
{
    if(animal[x]!=x)
    {
        int u=find(animal[x]);
        len[x]+=len[animal[x]];
        animal[x]=u;
    }
    return animal[x];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) animal[i]=i;
    while(m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if( x>n || y>n ) quantity++;
        else
        {
            int px = find(x);
            int py = find(y);
            if(op==1)//真话 x和y是同类
            {
                if(px==py && (len[x]-len[y])%3)
                    quantity++;
                else if(px!=py)
                {
                    //合并x和y所在集合
                    animal[px]=py;
                    /*因为合并x和y所在集合多出了一段长度
                    这块长度是find(x)到find(y)的距离
                    所以求多出来的这块部分的长度
                    当x和y是同类时,有这样的特性
                    (len[x]+len[find[x]]-len[y])%3==0
                    这里的len[x]是还未合并时,x到find[x]的距离
                    ∴len[find[x]]=len[y]-len[x]
                    */
                    len[px]=len[y]-len[x];
                }
            }
            else//真话 x捕食y
            {
                /*
                  当x和y在一个集合中时,由题目可知,x捕食y
                  此时有 
                  x到根节点的距离-y到根节点的距离=1+3k k为任意
                  实数
                  ∴当(len[x]-len[y]-1-3k)%3 ==0 时可确认
                  x捕食y
                  反之当(len[x]-len[y]-1-3k)%3 !=0 
                  x不可能捕食y
                */
                if(px==py && (len[x]-len[y]- 1) %3)
                    quantity++;
                else if(px!=py)
                {
                    //当x和y不在一个集合时,将x和y所在集合合并
                    animal[px]=py;
                    /*
                    设find(x)到find(y)的距离为len([find(x)])
                    此时有len[x]+len([find(x)])-len[y]=3k+1
                    ∴len[find(x)]=-len[x]+len[y]+1+3k
                    */
                    len[px]=len[y]+1-len[x];
                }
            }
        }
    }
    cout<<quantity;
    return 0;
}
 

Answer 1

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，目前超出我们的服务范围，暂时无法为您解答。

首次提问人员可免费体验一次有问必答服务。目前首次提问的问题服务范围为：编程语言、Java开发、python、数据库、前端开发 领域专业技术问题，为您提供问题的解决思路和指导。不提供源码代写、项目文档代写、论文代写、安装包资源发送或安装、软件使用指导等服务。

我们后续会持续优化，扩大我们的服务范围，为您带来更好地服务。