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

· · 题解

题目传送门

前置芝士：并查集、按秩合并。

首先对于题目：

多条道路

不用管它，因为是双向道路，所以可以：

1->2
2->1
1->2

只要联通就满足。

既然是连通性，很容易想到并查集。

对于操作 1 和 3 ，就是并查集的模版，如下：

//f[i]表示i的祖先
int find(int k)
{
    if(f[k]==k) return k;
    return find(f[k]);
}
//查找祖先的函数（不含路径压缩）
cin>>op>>x>>y;
if(op==1)
{
    x=find(x),y=find(y);//查找祖先
    if(x!=y) f[x]=y;//合并
}
else if(op==3)
{
    x=find(x),y=find(y);//查找祖先
    if(x!=y) cout<<"Yes\n";
    else cout<<"No\n";
  //判断是否在同一集合
}

重点在于操作 2 ：如何撤回合并操作？

发现对于如上的普通并查集，一次合并操作仅有 f_x=y ,所以每次的合并是将 x 为根的树合并至 y 下，因此每次合并就将 f_x 改回原来的值就好了。

因此可以记录一个栈，表示依次更改了 f_i 值的 i ，每一次撤销提出栈顶 k ，并 f_k=k ，删除栈顶。如果为空则无操作。但是如果合并过程中 x=y ，即两点处于同一集合中，那么栈中加入 0 表示删除无效果。

但是这里不能路径压缩，这样会改变 x 的子树，不保证答案的正确。

因此可以采用按秩合并，定义 dep_i 为 i 的并查集子树的深度，将 x 和 y 中较小深度的合并到深度较大的上，可以保证深度的最小化，每次查询最坏复杂度 O(\log{n}) 。

总复杂度 O(n+m\log{n}) ，可以通过 n,m \le 3 \cdot 10^5 。

#include <bits/stdc++.h>
using namespace std;
int n,m,op,x,y,f[300005],dep[300005],len,stac[300005];
//f表示节点的父亲 ，dep为子树深度，stac是栈，len是其长度 
int find(int k)
{
    if(f[k]==k) return k;
    return find(f[k]);
}
//查找祖先的函数，但不能路径压缩 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i,dep[i]=1;//赋初值不能忘（本人踩过的坑） 
    while(m--)
    {
        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[x]+1,dep[y]);//更新深度 
                stac[++len]=x;
            }
            else stac[++len]=0;
        }
        else if(op==2)
        {
            if(len>0)
            {
                int k=stac[len--];
                if(k) f[k]=k;//撤回操作，因为它是根，所以父亲是他自己 
            }
        }
        else
        {
            cin>>x>>y;
            x=find(x),y=find(y);
            if(x==y) cout<<"Yes\n";
            else cout<<"No\n";
        }
    }
    return 0;
}