目录

引入

初始化

查询

合并

启发式合并

删除

移动

复杂度

时间复杂度

空间复杂度

带权并查集

---

引入

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

顾名思义，并查集支持两种操作：

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

并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

初始化

初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。

struct dsu {
  vector<size_t> pa;

  explicit dsu(size_t size) : pa(size) { iota(pa.begin(), pa.end(), 0); }
};

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))

查询

我们需要沿着树向上移动，直至找到根节点。

size_t dsu::find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

def find(self, x):
    if self.pa[x] != x:
        self.pa[x] = self.find(self.pa[x])
    return self.pa[x]

合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。

void dsu::unite(size_t x, size_t y) { pa[find(x)] = find(y); }

def union(self, x, y):
    self.pa[self.find(x)] = self.find(y)

启发式合并

合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。

按节点数合并的参考实现：

struct dsu {
  vector<size_t> pa, size;

  explicit dsu(size_t size_) : pa(size_), size(size_, 1) {
    iota(pa.begin(), pa.end(), 0);
  }

  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) swap(x, y);
    pa[y] = x;
    size[x] += size[y];
  }
};

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))
        self.size = [1] * size

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.pa[y] = x
        self.size[x] += self.size[y]

删除

要删除一个叶子节点，我们可以将其父亲设为自己。为了保证要删除的元素都是叶子，我们可以预先为每个节点制作副本，并将其副本作为父亲。

struct dsu {
  vector<size_t> pa, size;

  explicit dsu(size_t size_) : pa(size_ * 2), size(size_ * 2, 1) {
    iota(pa.begin(), pa.begin() + size_, size_);
    iota(pa.begin() + size_, pa.end(), size_);
  }

  void erase(size_t x) {
    --size[find(x)];
    pa[x] = x;
  }
};

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size, size * 2)) * 2
        self.size = [1] * size * 2

    def erase(self, x):
        self.size[self.find(x)] -= 1
        self.pa[x] = x

移动

与删除类似，通过以副本作为父亲，保证要移动的元素都是叶子。

void dsu::move(size_t x, size_t y) {
  auto fx = find(x), fy = find(y);
  if (fx == fy) return;
  pa[x] = fy;
  --size[fx], ++size[fy];
}

def move(self, x, y):
    fx, fy = self.find(x), self.find(y)
    if fx == fy:
        return
    self.pa[x] = fy
    self.size[fx] -= 1
    self.size[fy] += 1

复杂度

时间复杂度

同时使用路径压缩和启发式合并之后，并查集的每个操作平均时间仅为O(a(n))，其中a

为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

Ackermann 函数A(m, n)的定义是这样的：

而反 Ackermann 函数 a(n)的定义是阿克曼函数的反函数，即为最大的整数 m 使得A(m, n) <= n。

空间复杂度

显然为 O(n)。

带权并查集

我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。比如对于经典的「NOI2001」食物链，我们可以在边权上维护模 3 意义下的加法群。