并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。 它支持两种操作：

• 查找（Find）：确定某个元素处于哪个子集；
• 合并（Union）：将两个子集合并成一个集合。

初始化

首先，在并查集初始化时，我们认为每一个元素都构成一个独立的子集，故每一个元素的父亲都是自己。

void makeSet(int size) 
{
  for (int i = 0; i < size; i++) fa[i] = i;  // i就在它本身的集合里
  return;
}

查找

每一个元素都能知道自己的父亲（上一级）是哪一个元素，如果再向父级查找父级，一直到一个父级为自身的元素时，就代表找到了祖先，那么就实现了并查集的查找算法。

int fa[MAXN];  // 记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己
int find(int x) 
{
  // 寻找x的祖先
  if (fa[x] == x)  // 如果x是祖先则返回
    return x;
  else
    return find(fa[x]);  // 如果不是则x的爸爸问x的爷爷
}

路径压缩

有了查找算法，我们就可以让所有的元素直接指向自己的祖先，而省去一层层询问的时间，对于新加入的元素，也只需要一次询问即可找到其祖先。

int find(int x) 
{
  if (x != fa[x])  // x不是自身的父亲，即x不是该集合的根
    fa[x] = find(fa[x]);  // 查找x的祖先直到找到根,于是顺手路径压缩
  return fa[x];
}

合并

如果出现两个独立的子集需要进行合并，使其中一个成为另一个的父亲，那么就需要进行合并，从上文可以知道，只需把其中一个祖先变成另一个祖先的儿子即可。

void join(int x, int y) 
{
  // x 与 y 所在家族合并
  x = find(x);
  y = find(y);
  fa[x] = y;  // 把 x 的祖先变成 y 的祖先的儿子
}

完整代码

int fa[MAXN];

int find(int x)
{
  if (x != fa[x])
    fa[x] = find(fa[x]);
  return fa[x];
}

void makeSet(int size)
{
  for (int i = 0; i < size; i++) fa[i] = i;
  return;
}

void join(int x, int y) 
{
  x = find(x);
  y = find(y);
  fa[x] = y;
}

接口

fa数组用于存储某个元素的祖先是谁，find函数用于寻找元素祖先并进行路径压缩，makeSet函数用于初始化，join函数用于合并新元素。

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/79.html
最后修改时间：2021-01-01 16:50:00
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！