蓝桥杯备考并查集
蓝桥杯备考：并查集
要学并查集，首先我们得知道什么是双亲表示法，我们之前学树的时候，是用的孩子表示法，双亲表示法又是什么呢？首先，我们的并查集实际上就是一个森林
双亲表示法就是把每个结点的双亲存下来，比如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;
}