[Data Structure]Union Find

Union Find是一种支持连接元素和查询任意两个元素是否相连的一种数据结构，直观的来讲Union Find就是几颗不同的多叉树，相连的元素共享相同的root，连接不同的元素只需要将两个多叉树相连，查询两个不同的元素是否相连我们只需查询他们时候有相同的root，其支持的操作如下:

• public void union(int p, int q) 把 p 和 q 连起来
• public int find(int p) 找到 p 的 root
• public boolean connected(int p, int q) 查看 p 和 q 是不是相连的

我们只需要用array即可表示，array[i]表示i节点的父节点，如图所示：

1. union

最简单的union操作就是从当前 p 和 q 一直找到 pRoot 和 qRoot，然后把 pRoot 的 parent设置成
Root，这样时间复杂度是 O (n)，如果连接的时候我们一直把 size 较小的那个 tree 连向 size 较
大的 tree，可以优化到 O(log n)，因此我们需要另外一个array记录以i为root的subtree的大小。

2. find

size balancing优化后的复杂度是 O(log n)，我们可以做的优化的是，在我们从 p 到 root 的过程中，
把路径上所有节点指向 root，通过一个简单的递归可以实现，从底部到 root，拿到 root 后再一层
一层 return 回来， 同时把路径上的节点指向 root。 经过 path compression 的优化后，时间复杂度，
可以达到 O(lg *n)，十分接近常数时间复杂度，如图所示，我们在find(9)的过程中不断地压缩经
过节点的路径：

3. connected

判断 p 和 q 的 root是不是相等即可

完整代码如下：