70TLE

osky123456 @ 2022-01-14 20:58:06

#include<bits/stdc++.h>
#define MAXN 10001
using namespace std;
int n,m,fa[MAXN];
int find(int x){
    return x==fa[x]?x:find(fa[x]);
}
int main(){
    int x,y;
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    while(m--){
        int data;
        cin>>data>>x>>y;
        if(data==2){
            if(find(x)==find(y)) 
            cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
        else{
            fa[find(x)]=find(y);
        }
    }
    return 0;
}

by Madsome @ 2022-01-14 21:01:02

没路径压缩

by osky123456 @ 2022-01-14 21:02:27

@jstzmxuan 我的find应该是路径压缩了吧

by 0htoAi @ 2022-01-14 21:03:01

@osky123456 没有就是没有。另外你还可以启发式合并

by Madsome @ 2022-01-14 21:03:04

是

return x==fa[x]?x:fa[x]=find(fa[x]);

by TheSky233 @ 2022-01-14 21:03:31

@osky123456 路径压缩

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

by osky123456 @ 2022-01-14 21:04:11

@0htoAi 启发式合并对于路径压缩好像平均复杂度差不多

by osky123456 @ 2022-01-14 21:04:37

@TheSky233 谢谢谢谢

by 0htoAi @ 2022-01-14 21:08:18

@osky123456 启发式合并是log，路径压缩也是log，但是启发式合并+路径压缩是反阿克曼函数。

by joy2010WonderMaker @ 2022-01-14 21:20:13

@0htoAi 其实不加上基本卡不掉

by joy2010WonderMaker @ 2022-01-14 21:20:51

因为像路径压缩这东西很难卡吧