引入 链接到标题
并查集是一种用于管理元素所属的集合的数据结构,其实现或者说表现为一片森林,其中,每棵树表示了一个集合,树中的节点表示对应的集合中的元素:
顾名思义,并查集支持两种操作:
- 合并(Union):合并两个元素所属的集合(合并对应的树);
- 查询(Find):查询某个元素所属的集合(即查询对应的树的根节点),这可以用于判断两个元素是否属于同一个集合;
并查集在经过修改后还可以支持单个元素的移动、删除;使用动态开点线段树还可以实现可持久化并查集;
初始化 链接到标题
初始时,我们设置每个元素都属于一个单独的集合,表示为一棵只有根节点的树,每个根节点的父亲都设置为自己。
class Dsu {
vector<size_t> parent_; // 表示每个节点的父节点
vector<size_t> size_; // 表示每棵树有多少节点
Dsu(size_t size) : parent_(size), size_(size, 1) {
iota(parent_.begin(), parent_.end());
}
}
查询 链接到标题
我们只需要沿着树向上移动,直到找到根节点
size_t Dsu::find(size_t x) {
return parent_[x] == x ? x : parent_[x];
}
查询时进行路径压缩 链接到标题
查询过程中,经过的每个元素都属于该集合,因此我们可以直接将其连接到根节点,以加快后续查询。
size_t Dsu::find(size_t x) {
return parent_[x] == x ? x : parent_[x] = find(parent_[x]);
}
合并 链接到标题
要合并两棵树,我们只需要将一棵树的根节点连接到另一棵树的根节点。
void Dsu::Unite(size_t x, size_t y) {
parent_(find(x)) = find(y);
}
启发式合并 链接到标题
即将节点较小或者深度较小的树连接到另一棵,这里以按节点数合并的实现作为参考:
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);
}
parent_[y] = x;
size_[x] += size_[y];
}