1回答

liuyubobobo

2021-05-05

已采纳

并查集的主要作用不是“存储数据”，而是“快速查询数据的状态或者关系”。这一点和线段树，包括后面会学习的 sqrt 分解有类似的地方。

具体来讲，并查集的作用是，快速响应对元素所处的集合进行合并操作，以及快速查询两个元素是否属于同一个集合。

并查集最典型的应用，可以参考 Kruskal 算法（一个最小生成树算法），Kruskal 算法中间需要不断地将两个点合并（并查集中的合并操作），并且快速判断两个点是否在一个环中（并查集中的查询操作）。如果没有并查集，Kruskal 算法是没有高效的实现方式的。Kruskal 算法其中快速判断一个边是否形成环，依赖并查集。可以参考我这篇文章中，4 里的介绍：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247484599&idx=1&sn=5f7bfd01d719e75c663211d5dbfb8cfe&chksm=fd8cabf1cafb22e7f58f865e29e941648fb24e8a3c261bf8cd80d7888fa21871330e9feb4918&token=377407044&lang=zh_CN#rd

==========

更一般的，在算法面试中，常见的使用并查集的情景，是动态地快速判断图中节点的连通性（两个节点是否在一个连通分量中）。大多数力扣上并查集的问题，都属于此类。如果有兴趣，可以过一遍力扣上并查集标签的问题：https://leetcode-cn.com/tag/union-find/problemset/

（这里并不是所有的问题都必须使用并查集，但是如果你能过一遍所有问题，一定能对并查集的使用场景有更深刻的认识的。）

==========

并查集还有更多的作为算法优化的高级应用，是面试级别的问题触及不到的。如果感兴趣，这里有一份很好地总结：https://cp-algorithms.com/data_structures/disjoint_set_union.html#toc-tgt-6

继续加油！：）

​

2