Union-Find

1.定义

数组和指针指向

时间复杂度O(log*n)，小于O(logn)，接近O(1)

2.目标

• 创建一个数组，记录每个节点的连接状态，从而解决在网络中两点间的连接状态(返回true, false，并不需要求出其路径)
• 数据的合并和查询

3.基本操作

public interface UF {
    int getSize();
    boolean isConnected(int p, int q);
    void unionElements(int p, int q);
}

4.优化

目标：减少高度

• size: 少到多
• rank: 矮到高

• find: parent[p] = parent[parent[p]]

• recursion:

if (p != parent[p])
    p = find(parent[p]);

code

https://github.com/nyannko/leetcode-java/tree/master/src/ds/unionfind