如何卡掉可撤销并查集按 dep 合并不回退 dep 的写法

Shunpower @ 2024-03-12 17:51:54

by Shunpower @ 2024-03-12 17:55:06

这些提交记录空间很大的原因是因为 push 进了栈但是不弹导致的内存堆叠，卡法不应该从这个方向入手。

by jason_sun @ 2024-03-12 17:59:22

感觉复杂度确实是根号的，数据还在写

by jason_sun @ 2024-03-12 18:03:54

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int fa[100005], dep[100005];
int st[500005], top;
int find_fa(int x){
    return fa[x]==x?x:find_fa(fa[x]);
}
void hb(int x, int y){
    x=find_fa(x), y=find_fa(y);
    if(dep[x]<dep[y]) swap(x, y);
    fa[y]=x;
    dep[x]+=(dep[x]==dep[y]);
    st[++top]=y;
}
void del(){
    int x=st[top]; top--;
    fa[x]=x;
}
int main(){
    int n=1000;
    for(int i=1; i<=n; ++i){
        fa[i]=i;
        dep[i]=1;
    }
    for(int i=2; i<=1e3; ++i){
        for(int j=1; j<i; ++j){
            hb(i, j);
            del();
        }
    }
    puts("A");
    for(int i=2; i<=1e3; ++i){
        hb(i, i-1);
    }
    puts("B");
    for(int i=1; i<=1e6; ++i){
        find_fa(1);
    }
    puts("C");
    return 0;
}

by jason_sun @ 2024-03-12 18:04:47

@Shunpower 表现为单次根号

by Shunpower @ 2024-03-12 18:06:06

@jason_sun 这么牛，thx

by jason_sun @ 2024-03-12 18:08:50

by Iniaugoty @ 2024-03-12 19:05:54

我觉得线段树分治板子怎么着也要加强一下，把复杂度错的做法卡掉