介绍

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

并查集支持两种操作：

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

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

参考：https://oi-wiki.org/ds/dsu/

实现

初始化

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

struct dsu {
  vector<size_t> pa;

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

查询（效率不佳）

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

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

查询+路径压缩

查询过程中经过的每个元素都属于该集合，所以我们可以将其直接连到根节点，以加快后续查询。

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