并查集总结

1、简介

1）有若干个样本 a、b、c、d… 类型假设是 V

2）在并查集中一开始认为每个样本都在单独的集合里

3）用户可以在任何时候调用如下两个方法：

• boolean isSameSet(V x, V y)：查询样本 x 和 样本 y 是否属于一个集合

• void union(V x，V y)：把 x 和 y 各自所在集合的所有样本合并成一个集合

4）isSameSet 和 union 方法的代价越低越好

2、并查集结构

1）每个节点都有一条往上指的指针

2）节点 a 往上找到的头节点，叫做 a 所在集合的代表节点

3）查询 x 和 y 是否属于同一个结合，就是看看找到的代表节点是不是一个

4）把 x 和 y 各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂在大集合的代表点的下方即可

(可以用哈希表或者数组实现，虽然二者的时间复杂度一致，但是哈希表实现方式的常数比数组实现的常数大2倍左右，所以在数据量很大的时候，数组的实现方式用时更少）

3、并查集的优化

1）节点往上找代表节点的过程，把沿途的链变成扁平的 【路径压缩】

说明：比如 a->b->c->f，即代表节点是 f，那么则将 a、b、c分别直接连到 f，变成了a->f、b->f、c->f

2）小集合挂在大集合的下面 【按秩合并】

说明：小集合挂在大集合下，链的长度增长得比较慢。所谓大小集合就是集合的元素个数，元素个数多的叫做大集合，小的叫做小集合。

3）如果方法调用很频繁，那么单次调用的代价为 $O(1)$，两个方法都如此

4、并查集的应用

• 解决两大块区域的合并问题
• 常用在图等领域中（连通性问题）