蒟蒻70分TLE求助!!!

P3367 【模板】并查集

Joker_Wang @ 2022-08-08 18:42:58

#include<bits/stdc++.h>
using namespace std;
int n,m;
int op,a,b;
int fa[200005];
int find(int x)
{
    if(x==fa[x]) return x;
    return find(fa[x]);
}
int main()
{
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>op>>a>>b;
        if(op==1)
        {
            fa[find(a)]=find(b);
        }
        else if(op==2)
        {
            if(find(a)==find(b))
            {
                cout<<"Y"<<"\n";
            }
            else
            {
                cout<<"N"<<"\n";
            }
        }
    }
}

by Jorisy @ 2022-08-08 18:46:31

int find(int x)
{
    if(x==fa[x]) return x;
    return find(fa[x]);
}

请路径压缩:

int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

by Joker_Wang @ 2022-08-12 12:42:18

@JYqwq 谢谢大佬指点


|