蓝桥杯备考:并查集

发布于:2025-03-16 ⋅ 阅读:(14) ⋅ 点赞:(0)

要学并查集,首先我们得知道什么是双亲表示法,我们之前学树的时候,是用的孩子表示法,双亲表示法又是什么呢?首先,我们的并查集实际上就是一个森林

双亲表示法就是把每个结点的双亲存下来,比如2结点的双亲是1,下标为2就放的是1

当我们把每个结点的父亲都存下来,就完成了

不过,在实现并查集的时候,我们一般都把根节点的双亲标志为它自己

并查集的概念:

并查集,就是合并集合,查询集合元素的一个数据结构

比如我们有三个集合

我们需要频繁进行三个操作①查询操作,我们每个集合都有一个代表元素,比如第一个集合代表元素就是1,第二个集合代表元素就是6,第三个集合代表元素就是8,我们要查询某个元素是位于哪个集合里

②合并操作,我们要合并某两个集合,参数就是两个代表元素

③判断操作,判断两个元素是不是在一个集合里,我们只要看两个元素的集合的代表元素是不是同一个就行了

比如find(11)就是8,find(9)也是8  find(3)是1,find(6)是7

thesame(10,11)是对的

union(7,2)就是合并6和1代表的俩集合

这就差不多是并查集要实现的功能

不过我们要真正实现并查集,必须要用到树,用到森林

我们需要把这些集合分别弄成每棵树,用双亲表示法表示,代表元素就是根节点

三大操作 一/find 我们只需要根据find的值不断向上找根节点就可

如图这就是我们find的函数,就是不断的向上找根节点不断的向上找根节点,当找到根节点的时候返回

二/union 我们只需要找到根节点,然后把一方的根节点挂在另一方即可

三/thesame 我们只要用两个find 比较根节点是不是一样的就行

但是仅仅这样还是不够的,我们想象出一个极端的例子

我们合并的时候,如果一直让长的挂在短的后面,就会形成一个类似链表的东西,这时候我们再进行查询就是O(N)级别的了

我们怎么优化?

我们可以让每次find的时候,在回溯的过程中,让遍历到的每个结点都变成这个根节点的孩子

差点忘记说了,我们的并查集是需要初始化的

完整代码

#include <iostream>
using namespace std;

void init()
{
	for(int i = 1;i<=n;i++)
	{
		fa[i] = i;
	}
}
int find(int x)
{
	if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
	//return fa[x] == x ? x  : find(fa[x]);
} 

void un(int x,int y)
{
	int px = find(x);
	int py = find(y);
	fa[px] = py;
}

bool thesame(int x,int y)
{
	return find(x) == find(y);
}

好,接下来我们来做一道模板题

#include <iostream>
using namespace std;
const int N  = 2e5+10;
int fa[N];
int n,m;
int find(int x)
{
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
	
}
void un(int x,int y)
{
	int dx = find(x);int dy = find(y);
	fa[dx] = dy;
}
bool isthesame(int x,int y)
{
	return find(x) == find(y);
}
int main()
{
	cin >> n >> m;
	for(int i = 1;i<=n;i++)
	{
		fa[i] = i;
	}
	while(m--)
	{
		int op,x,y;cin >> op >> x >> y;
		if(op == 1) un(x,y);
		else if(op == 2)
		{
			if(isthesame(x,y)) cout << "Y" << endl;
			else cout << "N" << endl;
		}
		
	}
	
	
	
	
	
	return 0;
}


网站公告

今日签到

点亮在社区的每一天
去签到