可撤销并查集只可以按照加入的时间从后到前撤销加边操作。
具体的,我们会把所有加入的边压入一个栈,然后当什么时候要撤销时不断从栈顶弹出一条边,撤销掉。而至于具体的撤销步骤,我们假设此边原来是把 y 连向 x,那么我们直接把 y 的父亲设为 y 本身,因为在合并两个集合时是把两个端点都执行了一遍找祖先的操作,所以 y 必定作为其原集合的祖先。我们再把 x 的子树大小减去一个 y 的子树大小,那么就还原成功了。
那么对于一条边为什么一定要是有顺序的撤销呢?如果不是按出栈的顺序撤销,那么必定有比他晚一些连边的集合的大小没法维护,所以必须按出栈顺序撤销。
fromzac
int find(int x){return x==fa[x]:x:find(fa[x]);}void merge(int u,int v){int fu=find(u),fv=find(v);if(fu==fv){return ;}if(sz[fu]<sz[fv]){swap(fu,fv);}stk[++top]=fv;fa[fv]=fu;sz[fu]+=sz[fv];
}void del(){if(!top)return ;int v=stk[top];top--;sz[fa[fv]]-=sz[fv];fa[fv]=fv;
}while(top>tmp)del();