P12274 [蓝桥杯 2024 国 Python B] 设计 题解

· · 题解

题目传送门：P12274 [蓝桥杯 2024 国 Python B] 设计

@123456wjc 说：“一想到二十年后如果 OI 还在，所有的小孩都必须人手掌握路径压缩和按秩合并，我就感到悲伤。”。

题目分析

题目要求查询连通性，所以考虑用并查集维护。

操作 1：合并 x_i 和 y_i 所属的集合。

操作 3：查询 x_i 和 y_i 是否在同一个集合内。

这两个可以轻松用并查集实现，不会的出门右转模板题。我们的重点在于操作 2，如何实现最近操作的撤销？

定义 f_x 为 x 所在集合的祖先，则合并前 f_{f_x}=f_x。发现（在朴素的并查集下），一次合并会使 f_x \leftarrow y，因此我们撤销时，只要让它变回自身就行了。

故使用栈维护：存储每次修改的 f_x 位置，合并时入栈，遇到操作 2 就将栈顶的 f 变回自身。特殊地，如果合并前 x 和 y 就在同一集合，则撤销对其没有影响，可以入栈一个特殊值（如 0）。

但是这样的并查集是无法路径压缩的，否则正确性就不保了。但朴素的并查集又会超时，于是考虑按秩合并。

按秩合并：对于并查集的两个树形集合 x,y，维护它们的深度，每次将深度小的合并到深度大的上。这样可以保证查询的最劣复杂度是 O(\log n)。

最终复杂度为 O(n + m\log n)。

代码实现

#include<iostream>
#include<stack>
using namespace std;
const int N=300005;
int n,m,f[N],dep[N];
int find(int x){
    if(f[x]==x)return x;
    return find(f[x]);
}
stack<int>t;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)f[i]=i,dep[i]=1;
    while(m--){
        short op;
        int x,y;
        cin>>op;
        if(op==1){
            cin>>x>>y;
            x=find(x),y=find(y);
            if(x!=y){
                if(dep[x]>dep[y])swap(x,y);
                f[x]=y,dep[y]=max(dep[y],dep[x]+1);
                t.push(x);
            }
            else t.push(0);
        }
        else if(op==2){
            if(t.empty())continue;
            x=t.top();
            t.pop();
            if(x)f[x]=x;
        }
        else{
            cin>>x>>y;
            cout<<(find(x)==find(y)?"Yes":"No")<<'\n';
        }
    }
    return 0;
}

AC 记录。