数据结构里汇集了很多种存储结构，包括线性表、树、图等，它们还可以进行更细致地划分，每一种结构都有其特定的用途和优势。
拿最简单的线性表举例，它专门存储逻辑关系是“一对一”的数据。线性表又可以细分为顺序表和链表，顺序表擅长对目标元素的查询操作，而链表擅长对目标元素的添加（插入）和删除操作。
本节给大家讲解的并查集，也是一种存储结构，它可以存储多个集合，特别擅长处理集合的合并（Union）和查询（Find）操作。
这里提到的集合，与数学里的集合非常类似，可以存放一组元素，它的特点是：
- 集合中的每个元素都是独一无二的，集合里不允许存在重复的元素；
- 集合中的元素是没有顺序的。
例如，{1, 2, 3} 是一个集合，它和{3, 1, 2}是同一个集合，因为它们包含相同的元素。
集合的合并操作，指的是将两个独立的集合整合成一个大的集合，比如将 {1, 2} 和 {3} 合并为 {1, 2, 3}；集合的查询操作，指的是查找目标元素属于哪个集合。
搞清楚并查集是什么之后，接下来讲解并查集的具体实现。
并查集的实现
并查集可以存储多个集合，它能够高效地完成集合的合并和查询操作。
给定一个并查集，我们可以把它里面的每个集合想象成一棵树结构（注意不是二叉树，是多叉树），那么整个并查集就是一个森林。假设{0, 1, 2, 3, 4} {5, 6, 7} {8}是一个并查集，它是一个包含 3 棵树的森林，如下图所示：
图 1 想象成森林的并查集
在图 1 的基础上，可以很轻松地完成集合的合并和查询操作：
1) 合并两个集合，只需要找到它们各自的树根结点，再把两个树根结点相连即可，如下图所示：
图 2 集合的合并操作
图中，r 指的是整棵树的高度（深度）；s 指的是树中的结点数量。
像图 2 这样，通过连接两棵树的根结点，把两棵树整合成一棵树，就实现了把两个集合{0, 1, 2, 3, 4} {5, 6, 7}合并成一个集合{0, 1, 2, 3, 4, 5, 6, 7}。
2) 查询某个元素位于哪个集合，等同于确定该元素位于哪棵树上。我们习惯选择树根结点代表整棵树（把位于树根的元素作为整个集合的代表），因为只要树的根结点存在，整棵树就一直存在。
仔细观察图 2，两棵树未整合之前，元素 5 位于根结点是 6 的树上（5 位于代表元素是 6 的集合里）；两棵树整合之后，元素 5 所在的树成为了另一棵树的一部分，元素 5 就位于根结点是 3 的树上（5 位于代表元素是 3 的集合里）。
在上述的讲解中，我们把并查集想象成是森林，把并查集里的集合想象成一棵棵的树，实现了集合的合并和查询操作。然而真正落地、写代码实现并查集，用的不是复杂的树形结构，而是顺序表（一维数组）。
假设并查集内有 3 个集合，分别是{0, 1, 2, 3, 4}、{5, 6, 7} 和 {8}。想要将这 3 个集合存放到数组里，除了存储所有元素的值之外，还要存储各个元素之间的关系，存储方案是：
- 将并查集里的每个元素各自对应一个数组下标。换句话说，用数组下标代表并查集里的元素；
- 把每个集合想象成一棵树，数组中负责记录各个元素的父亲结点的位置下标。树根结点比较特殊，它没有父亲结点，它对应的数组空间里存储的是自己的位置下标。
存储{0, 1, 2, 3, 4} {5, 6, 7} {8}的并查集如下图所示：
图 3 存放多个集合的数组
仔细观察图 3 下方的数组：
- 下标 0 处存储的值是 2，表明元素 0 和 2 位于同一个集合里；
- 下标 1 存储的值是 3，表明 1 和 3 位于同一个集合；
- 下标 2 存储的值是 3，表明 2 和 3 位于同一个集合；
- 下标 3 存储的值是 3，它存储的是自己的下标值，表明它是一个树根结点，换句话说，它是一个集合的代表元素；
- 下标 4 存储的值是 3，表明 4 和 3 位于同一个集合。
0 和 2、2 和 3、1 和 3、4 和 3 都位于同一个集合，表明 {0, 1, 2, 3, 4} 是并查集中的一个集合，并且这个集合的代表元素是 3。同样的道理，可以得出 {5, 6, 7} 是一个集合，代表元素是 6；{8} 是一个集合，代表元素是 8。
你看，一维数组既存储了并查集中的全部元素，又存储了元素之间的关系，确实成功地存储了一个并查集。并查集可以用如下的 C 语言结构体表示：
- typedef struct {
- int parent[MAX_SIZE];
- int count;
- }UnionFind;
parent[] 数组用来存储并查集，count 用来统计并查集中的集合数量。
那么，如何在一维数组中实现集合的合并和查询操作呢？
仔细观察图 2，合并两个集合的过程，其实只做了一件事，就是把两个集合的代表元素（树根结点）连接起来。因此，合并数组中的两个集合，只需要做两件事：
- 找到两个集合中的代表元素，假设是 x 和 y；
- 把 x 的父结点改成 y，或者把 y 的父结点改成 x，都可以实现 x 和 y 建立连接。
