并查集

并查集：(union-find sets)是一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数、最小公共祖先、带限制的作业排序，还有最完美的应用：实现Kruskar算法求最小生成树。

从字面意思上理解，支持合并和查找操作的集合。

其主要是用来判断联通问题，也就是图中两点间是否存在道路可以连通。

并查集主要分为两种基本操作：

1. 合并（Union/Merge）：合并两个集合。
2. 查询（Find/Get）：查询元素所属集合。

并查集的概念

在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：

• 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
  
• 合并：将两个集合合并为一个。
  
• 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。

理解下面三句话，并查集就学会了：

“并”的意思是把两个处在同一个连通分量的结点给并到一起.

“查”的意思是查找一个结点的根节点.

“并”的时候需要用到“查”

不过这样还是比较晦涩。下面我们用图片的方式来讲讲。

图解并查集

并查集的重要思想在于，用集合中的一个元素代表集合。

刚开始好比诸侯国，各自为政。

后来3号被1号吞并了，定都1号城池。

同时2号也被1号吞并了，定都1号城池。

神州大地上 4，5，6也发生着相同的事情，5，6也背4号诸侯吞并了，定都4号城池。

后来1号把4号给吞并了，5，6也连带成了1号的领土。定都1号城池。

学习过前面的二叉树，其实我们可以把并查集想象成一个数的结构。

要寻找集合的代表元素（都城），只需要一层一层往上访问父节点（图中箭头所指的圆），直达树的根节点（图中橙色的圆）即可。

并查集路径压缩