RE?

P3367 【模板】并查集

陈皮宇宙总统 @ 2017-08-08 16:13:37

#include<iostream>
#include<cstdio>
#define maxn 5001
using namespace std;
int fa[maxn];
int m,n,x,y,z;
int find(int x)
{
    if(fa[x]!=x)return find(fa[x]);
    else return x;
}
void unio(int r1,int r2)
{
    fa[r2]=r1;
}
void pan(int x,int y)
{
    if(find(x)==find(y))cout<<"Y"<<endl;
    else cout<<"N"<<endl;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>z>>x>>y;
        if (z==2)pan(x,y);
        else if (z==1)
        {
            int r1=find(x);
        int r2=find(y);
        if (r1!=r2)unio(r1,r2);
        }
    }
    return 0;
}

by 陈皮宇宙总统 @ 2017-08-08 16:34:07

数组改大以后就是TLE了。。。


by Neo_Kylinson @ 2017-08-17 21:46:41

+1s


by 饮溪 @ 2017-08-21 19:48:12

没有写路径压缩


by 饮溪 @ 2017-08-21 19:49:32

@陈皮宇宙总统

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

by 陈皮宇宙总统 @ 2017-08-21 20:30:59

感谢大神


|