求助。#2#9#10超时怎么解决

shipeiqian @ 2022-07-08 16:35:11

#include <iostream>
using namespace std;
int fa[100005];
int n,m,k;
int fi(int x){//查找 
    if(x==fa[x])return x;
    return fi(fa[x]);
}
bool check(int x,int y){
    int fx=fi(x),fy=fi(y);
    return fx==fy;
}
void merge(int x,int y){//合并
    if(check(x,y))return ;
    int fx=fi(x),fy=fi(y);
    fa[fx]=fy;

}
int main(){
    cin >>n >>m;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin >>x >>y >>z;
        if(x==1){
            merge(y,z);
        }
        else{
            if(check(y,z))cout <<"Y\n";
            else cout <<"N\n";
        }
    }
    return 0;
}

by AKNOI的梓钦 @ 2022-07-08 16:37:59

#include <iostream>
using namespace std;
int fa[100005];
int n,m,k;
int fi(int x){//查找 
    if(x==fa[x])return x;
    return fa[x]=fi(fa[x]);//这里存储一下，下次可以直接调用就不用再去递归了
}
bool check(int x,int y){
    int fx=fi(x),fy=fi(y);
    return fx==fy;
}
void merge(int x,int y){//合并
    if(check(x,y))return ;
    int fx=fi(x),fy=fi(y);
    fa[fx]=fy;

}
int main(){
    cin >>n >>m;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin >>x >>y >>z;
        if(x==1){
            merge(y,z);
        }
        else{
            if(check(y,z))cout <<"Y\n";
            else cout <<"N\n";
        }
    }
    return 0;
}

by Engulf @ 2022-07-08 16:38:09

路径压缩，

by AKNOI的梓钦 @ 2022-07-08 16:41:18

@TMJYH09 这，一道 {\color{orang}\text{普及-}} 也需要路径压缩。。。

by liangbowen @ 2022-07-08 16:42:51

@AKNOI的梓钦 路径压缩加几个字符而已，很合理吧。。

by _Remake_ @ 2022-07-08 16:42:53

@AKNOI的梓钦 不用路径压缩复杂度就假了吧(

by AKNOI的梓钦 @ 2022-07-08 16:44:17

哎，没有关系，单方面宣布此帖结。