问一下大佬,我这样算路径压缩吗?

P3367 【模板】并查集

artalter @ 2020-09-20 18:51:25

我看其他讨论说不路径压缩会TLE,可我的代码却AC了

#include<iostream>
using namespace std;
struct s{
    int a[100001]={}; 
    void push(int x,int y)
    {
        if(a[x]==0&&a[y]==0)
        {
            a[x]=y;
            a[y]=y;
         } else if(a[x]==0&&a[y]!=0)
         {
            if(a[y]!=y)
                a[x]=find(y);
            else 
                a[x]=y;
         }else if(a[y]==0&&a[x]!=0)
         {
            if(a[x]!=x)
                a[y]=find(x);
            else 
                a[y]=x;
         }else
         {
            if(!bmp(x,y))
            {
                a[find(x)]=find(y);
            }
         }
    }
    bool bmp(int x,int y)
    {
        if(x==y)return 1;
        if(a[x]==0||a[y]==0)return 0;
        if(find(x)==find(y))
        {
            return 1;
        }
        return 0;
    }
    int find(int x)
    {
        int ax=x;
        while(a[ax]!=ax)ax=a[ax];
        return ax;
    }
    void print(int x)
    {
        int ax=x;
        while(a[ax]!=ax)
        {
            cout<<ax<<"->";
            ax=a[ax];
        }
        cout<<ax;
        cout<<endl;
    }
};
int n,m,p;
int main()
{
    s a;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int z,x,y;
        cin>>z>>x>>y;
        if(z==1)
        {
            a.push(x,y);
        }
        if(z==2)
        {
            if(a.bmp(x,y))
            {
                cout<<"Y"<<endl;
            }else
            {
                cout<<"N"<<endl;
            }
        }
    }
    return 0;
}

by SIXIANG32 @ 2020-09-20 18:55:09

康不懂代码(恼


by pocafup @ 2020-09-20 18:57:51

这就是路径压缩吧


by artalter @ 2020-09-20 19:06:39

萌新初学数据结构,对于有的地方不太懂,感谢大佬


by 试试事实上吗 @ 2020-09-20 19:11:44

并查集是高级数据结构(参见算导)


by Seauy @ 2020-09-20 19:17:30

是的啊是的啊


by Ztemily @ 2020-09-20 19:20:51

大雾


by Jekyll_Y @ 2020-09-20 19:46:09

别问,问就是玄学(手动狗头)


by CAPTCHA_Ma @ 2020-09-22 20:50:33

害怕


by LordLaffey @ 2020-09-27 19:38:46

你应该感谢你push里的一大群 大妈if们((


by 冬刃 @ 2020-11-18 18:50:20

好长啊,看不懂


|