并查集

发表于 更新于 分类于 ， 阅读次数： 本文字数： 325 阅读时长 ≈ 1 分钟

并查集的定义

并查集（Union Find）：一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。不交集指的是一系列没有重复元素的集合。

并查集主要支持两种操作：

  • 合并（Union）：将两个集合合并成一个集合。
  • 查找（Find）：确定某个元素属于哪个集合。通常是返回集合内的一个「代表元素」。

实现

查找

确定某个元素属于哪个集合

1
2
3
4
int find(int x)
{
    return fa[x] == x ? x : find(fa[x]);
}

带路径压缩的查找

查找同时顺便修改父节点为根

1
2
3
4
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

合并

1
2
3
void unite(int x, int y){
	fa[find[x]] = find(y);
}

按秩合并（启发式合并）

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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];
  }
};

参考链接

C01【模板】并查集 - 董晓算法