3个TLE,实在不知道哪错了

Iverson_ @ 2022-08-19 16:11:06

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,z,x,y;
int p[10010];
int find(int a)
{
    if(p[a]!=a) return find(p[a]);
    return p[a];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>z>>x>>y;
        if(z==1) p[find(x)]=find(y);
        else{
            if(find(x)==find(y)) printf("Y\n");
            else printf("N\n");
        }
    }
    return 0;
 } 

by ssytxy2024 @ 2022-08-19 16:14:53

要路径压缩，不然可能会卡到 O(n)。

把find改成这样就可以了。复杂度应该是 O(\log n) 的。

int find(int k){
    if(p[k]==k) return k;
    return p[k]=find(p[k]);//把k到祖先这一条路径上的点的父亲都设为祖先。
}

by Iverson_ @ 2022-08-19 16:16:33

@qlzx74lyc41 orzorz

by _XHY20180718_ @ 2022-08-23 23:14:41

@Iverson_ 要按秩合并，不然其他题可能会卡 O(\log (n))

把

p[find(x)]=find(y);

改成

{
        int u=find(x);
        int v=find(y);
        if(sz[u]<sz[v]) swap(u,v);
        p[v]=p[u];
        sz[u]+=sz[v];
 }

现在是 O(a(n)) 的了。

记得加上sz(秩/结点数)数组