高手都爱用的算法：并查集（上）

有一类问题，如果不知道对应的算法，你可能都不知道从何入手，比如下面这个问题：

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。要求：输出所有学生中的已知的朋友圈总数。

我们先从简单的情形看看
比如班上有5个人，1和2是朋友，2和4是朋友，1和5也是朋友，3没有朋友，那么班上的朋友圈数量为2，如下图所示：

并查集.001

4和5由于传递性，最终都可以认为是1的朋友（4经过2传递到了1），所以是一个圈子的；3由于没有和任何人是朋友关系，所以自己是一个圈子。

三个性质

从上面的分析可以看出这类问题有以下特点：

1. 自反性：圈子里的人，自己也能成为一个圈子。
2. 对称性：A是B的朋友，B自然是A的朋友。
3. 传递性：如同题目描述的，A 是 B 的朋友，B 是 C 的朋友，那么 A 也是 C 的朋友。

这样形成的圈子，我们广泛地称为“不相交集合”，可以用树状结构来表示：

并查集.002

这种树的特点是：只由叶子向根遍历，也就是说每个节点只关心父节点是谁，而不关心它的子节点和其他关系，这样就可以用数组来表示，简化存储结构：

并查集.003.jpeg
数组下标表示自己的编号，数组里存放的是各自的父节点，-1表示父节点就是自己（图中为好理解，编号从1开始，实际数组下标从0开始，请自行转换）。

两个关键操作

1. 联合操作：

把两个集合合并到一起的操作就是联合操作，过程如下图所示：

并查集.004
初始状态表示每个节点本身是一个集合，符合自反性特征。

2. 查找集合操作：

一般简称为查找，这里想强调查找结果是集合的代表，就是每棵树的根，联合操作实际上是两个根的关联过程。

联合A和B集合时，到底谁当老子，也就是说选A还是B当合并后的根，这里面大有讲究，下篇我们就来聊聊合并的两种策略，并用Swift实现并查集的全过程，敬请关注。