Union Find

并查集（Union Find） 是一种图的算法，用于处理图中的不相交的节点的合并与查询问题。从中文语义来理解，Union Find → Find Union → 查找并集。其主要算法过程由三部分组成：

1. 添加： 添加一个元素到某一集合，一开始基本为将元素添加到自身一个元素的集合中。
2. 查找： 查询一个元素属于哪个集合，一般返回集合内的一个根元素，集合中所有元素都与该根元素相连。
3. 合并： 对于相连的两个节点，如果其处在不同集合中，则合并两个集合，一般为每个集合维持一个 Ranks 的变量，表示集合中节点的数量，将节点数较少的集合合并到节点数较多的集合当中，即将较少节点数的集合的根元素的根设置为较多节点数的集合的根元素，并更新对于的 Ranks。

添加操作的伪码：

 function MakeSet(x)
     x.parent := x
     x.rank := 0
 end function

查找操作的伪码：

 function Find(x)
     if x.parent = x then
         return x
     else
         x.parent := Find(x.parent) // 路径压缩，缩短 x 到根的距离
         return x.parent
     end if
 end function

按照 Rank 大小合并的伪码：

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)

     if xRoot != yRoot then
         if xRoot.rank < yRoot.rank then
             large := yRoot
             small := xRoot
         else
             large := xRoot
             small := yRoot
         end if

         small.parent := large
         large.rank = large.rank + small.rank
     end if
 end function

并查集运用的具体例子可参看：LC547 省份数量，LC684 冗余连接。