8个MLE,求助!!

P3367 【模板】并查集

Boar @ 2020-08-04 09:01:49

#include<bits/stdc++.h>
using namespace std;
struct Node{
    unsigned short pre;
}a[10000];
int fnd(int p){
    return a[p].pre==p?p:fnd(a[p].pre);
}
void crp(int p){
    a[p].pre=fnd(p); 
}
void mrg(int x,int y){
    int xp=fnd(x);
    a[xp].pre=y;
}
bool rlt(int x,int y){
    return fnd(x)==fnd(y);
}
int main(){
    unsigned short n;
    int m;
    for(int i=0;i<10000;i++) a[i].pre=i; 
    cin>>n>>m;
    for(int z,x,y,i=0;i<m;i++){
        cin>>z>>x>>y;
        if(z==1) mrg(x,y);
        else cout<<(rlt(x,y)?'Y':'N')<<endl;
    }
    return 0;
}

by liujiageng @ 2020-08-04 09:08:00

路径压缩呢


by Meowco @ 2020-08-04 09:32:55

void mrg(int x,int y){
    int xp=fnd(x);
    a[xp].pre=y;
}

这一步导致MLE

void mrg(int x, int y) {
    int xp = fnd(x);
    a[xp].pre = fnd(y);
}
int fnd(int p){
    return a[p].pre==p?p:fnd(a[p].pre);
}

这一步会导致TLE

int fnd(int p) {
    return a[p].pre == p ? p : a[p].pre = fnd(a[p].pre);
}

初始化

for(int i=0;i<10000;i++) a[i].pre=i;

for (int i = 1; i <= 10000; i++) a[i].pre = i;

by Boar @ 2020-08-04 10:39:28

@RBpencil 谢谢,已经过了


|