并查集

并查集是一种维护集合的数据结构，用于处理一些不相交集合的合并及查询问题，主要有查找和合并两种操作。

看一个具体的问题，已知一系列关于变量的等式，比如a==b, b==c, ...，问你其中两个变量是否相等，比如a和c是否相等？

示例1：

已知 a==b, b==c，问a==c是否成立?

示例2:

已知 a==b, c==d, b==e, e==c，问a==c是否成立？

思路是维护多个分组，将相等的变量划分到同一组，判断两个变量是否相等，只需要看他们是否属于同一个组。

问题是如何去维护这个分组？遍历等式时，首先需要查询等式两边的变量是否属于同一个分组，这就需要去查询所有的分组，看看两个变量是否属于同一个分组，有下面两种情况

1. 左右两边的变量目前已经属于同一个分组，不用处理。
2. 左右两边的变量目前属于不同的分组，需要将这两个分组合并。

上面提到的查询分组，还有合并分组，如果不使用并查集，操作起来就比较麻烦，而且效率低下，下面看看代码实现。

并查集就是为了简化多个集合查询和合并的，并查集是通过指向来维护集合，如果最终指向相同则说明他们属于同一个集合，最后一个元素指向自身，比如

• a->b或者b->a，说明a和b是属于同一个集合。
• c->d->e、c->e->d、d->c->e、....，说明c、d和e属于同一个集合。

如果要合并这两个集合a->b和c->d->e，只需要将b指向e即可，如下图

上述的问题用并查集实现，代码如下

上面代码实现了并查集功能，但是并未做优化处理，在合并两个集合时，一般需要考虑将层级较少的根元素指向层级较多的根元素。比如上面两个集合a->b和c->d->e，一般我们会让b指向e，而不是让e指向b，因为这样可以减少合并后整体的层级。