[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是不是相等即可

完整代码如下：

	public class UnionFind {
	private int[] id;
	private int[] sz;
	public UnionFind(int size) {
	id = new int[size];
	sz = new int[size];
	for(int i = 0; i < size; i++) {
	id[i] = i;
	sz[i] = 1;
	}
	}
	public void union(int p, int q) {
	int pRoot = find(p);
	int qRoot = find(q);
	//size balancing
	if (sz[pRoot] <= sz[qRoot]) {
	id[pRoot] = qRoot;
	sz[qRoot] += sz[pRoot];
	}
	else {
	id[qRoot] = pRoot;
	sz[pRoot] += sz[qRoot];
	}
	}
	public int find(int i) {
	if (id[i] == i)
	return i;
	//path compression
	int parent = find(id[i]);
	id[i] = parent;
	return parent;
	}
	public boolean connected(int p, int q) {
	return find(p) == find(q);
	}
	public int size() {
	return id.length;
	}
	}

view raw union find.java hosted with ❤ by GitHub