并查集

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

这三棵树可以组成一个森林，而这个森林可以叫并查集，每棵树可以称为并查集分量，这是逻辑上的理解

显式上理解，大部分情况并查集是以数组的方式进行存储的

有一些如下性质

每一个并查集分量（也就是每一棵树）都有一个根结点，比如上面三棵树的根结点分别是1，2，10 所属同一个并查集分量的结点的根结点是相同的，比如6，7，8的根结点都是10，所以这三个结点位于同一个并查集分量内，也就是同一颗树上 并查集每一个分量都是相互独立，互不影响的！ 并查集内所有节点的值一定是互不相同的

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

顾名思义，并查集支持两种操作：

合并（Union）：合并两个元素所属集合（合并对应的树） 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合 并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

并查集无法以较低复杂度实现集合的分离。