数据结构-并查集

并查集

参考资料:并查集 - OI Wiki

基本概念

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

显然，并查集支持两种操作:

  • 合并(union): 合并两个元素各自所属的集合
  • 查询(find): 查询某个元素所属的集合

初始化

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

1
2
3
4
struct dsu{
    vector<size_t> pa;
    explicit dsu(size_t size):pa(size){iota(pa.begin(),pa.end(),0);}
}

查询

我们需要沿着树向上移动，直至找到根节点。由于根节点的父亲是自己本身，因此递归的终止应该是pa[x] == x。

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

路径压缩

查询操作的目的是找到该元素的根节点，它和其它元素如何联系并不重要。因此，我们可以将查询过程中的每个元素直接连接到根节点（更改其父节点为根节点），减小了树的深度，加快了后续查询。

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