并查集模板代码(含有详细注释)

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 顾名思义，并查集支持两种操作： 合并（Union）：合并两个元素所属集合（合并对应的树） 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合 并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。 初始化 初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。 查询 我们需要沿着树向上移动，直至找到根节点。 路径压缩 查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询。 合并 要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。 移动 与删除类似，通过以副本作为父亲，保证要移动的元素都是叶子。 这是并查集的模板代码,里面详细解读了并查集，并附带了注释