今�Hの国の呵呵君: [Data Structure]Union Find

今�Hの国の呵呵君: [Data Structure]Union Find

[Data Structure]Union Find

支持的操作如下:

• 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 是不是相连的

1. union

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

2. find

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

3. connected

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

Read full article from 今�Hの国の呵呵君: [Data Structure]Union Find