【笔记】带权并查集

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

其支持两种操作：

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

CPP

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

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

CPP

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

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

CPP

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

时间复杂度为

O(m\times \alpha(n))

。

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

例：令

d_x

为节点

x

到父节点

fa_x

的距离，这样距离的计算方式是累加，在路径压缩的时候，我们只需要不断累加路径总长，最后压缩即可。

CPP

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

文章操作