【笔记】带权并查集

NEKO_Daze · 2025-08-10 21:38:47 · 算法·理论

1. 并查集

介绍

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合的元素。

其支持两种操作：

1. 合并(Union)：合并两个元素所属集合（合并对应的树）；
2. 查询(Find)：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合。

初始化及基本操作

初始时，每个元素都位于一个单独的集合，每个节点的父亲指针都指向自己

for(int i=1;i<=n;++i) fa[i] = i;

查询当前元素所在树的根节点，我们需要沿着树向上移动，直至找到根节点。

int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}//路径压缩

合并二者所在集合，需要找到二者的所在树根节点，然后，将二者根节点相连即可。

int fax=getfa(x), fay=getfa(y);
fa[fax]=fay;

时间复杂度为 O(m\times \alpha(n))。

2.带权并查集

我们在普通的并查集基础上，在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。

例：令 d_x 为节点 x 到父节点 fa_x 的距离，这样距离的计算方式是累加，在路径压缩的时候，我们只需要不断累加路径总长，最后压缩即可。

int getfa(int x)
{
  if (fa[x]==x) return x;
  int p=getfa(fa[x]);
  d[x] += d[fa[x]];
  return fa[x] = p;
}