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

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

首先对于题目：

CPP

多条道路

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

CPP

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

只要联通就满足。

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

对于操作

1

和

3

，就是并查集的模版，如下：

CPP

//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

。

CPP

#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;
}

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

文章操作

相关推荐

评论

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