并查集是什么数据结构？

本文共计600个文字，预计阅读时间需要3分钟。

并查集是一种多叉树，用于处理一些不相交集合的合并与查询问题。

初始化：每个节点单独作为一个集合。

查询：求元素所在的集合的代表元素，即根节点。

合并：将两个元素所在的集合合并。

并查集是一种多叉树，用于处理一些不相交集合的合并与查询问题。

初始化

每个结点单独作为一个集合。

查询

求元素所在集合的代表元素，即根结点。

合并

将两个元素所在的集合合并为一个集合。

合并之前，应先判断两个元素是否属于同一集合，用上面的查询来实现。

实现流程

动态集合中每一个元素由一个对象来表示，设x表示一个对象，并查集的实现需要如下操作：

MAKE(X)

建立一个新的集合，由于各集合是分离的，要求x没有在其他集合中出现过。

UNION(X,Y)

将包含x和y的动态集合合并为一个新的集合，假定在此操作前这两个集合是分离的。

所得集合的代表是Sx∪Sy的某个成员。

FIND(X)

返回包含x的集合的代表。