动态联通性问题----union-find算法

定义union-find算法API：

public class UF{               UF(int N)                          初始化N个触点       void union(int p,int q)            在p和q之间建立连接          int find(int p)                        p所在的分量的标识符 boolean connected(int p,int q)     p和q同在一个分量中则为true          int count()                             连通分量的数量 }

初始状态，每个触点都是一个分量。两点之间建立连接后，union()方法会将两个分量合并，一个分量中各触点都相互连接。find()方法返回给定触点所在连通分量的标识符。

此份API中，构造函数和count()方法很好写，connected方法只含有一条语句，即return find(p)==find(q);

数据结构：采用数组来实现。初始时数组各个元素保存自己的下标。

所以关键是实现find()方法和union方法。

1、quick-find算法

quick-find算法保证在同一连通分量中所有触点id[]中的值必须相同，这样connected()方法只需判断id[p]==id[q]即可。

find方法只需return id[p]; 而将两个连通分量合并，union()必须遍历数组，将一个连通分量中的id[]值变为另一个连通分量的id[]值。

public int qk_find(int p) {
	return id[p];
}
	
public void qf_union(int p,int q) {
	int pID = qk_find(p);
	int qID = qk_find(q);
	if(pID == qID) return;
	for(int i = 0;i<id.length;i++)
		if(id[i] == pID) id[i] = qID;
	count--;
}

算法分析：

在quick-find算法中，每次find()调用访问一次数组，归并两个分量的union()操作访问数组次数在（N+3）到（2N+1）之间。

假设最后只得到一个连通分量，至少需要N-1次union操作，（N+3）*（N-1）~N^2, 算法是平方级别的。

2、quick-union算法

quick-union算法中每个触点所对应的id[]元素都是另一个触点的名称（也可能是自己，如果是自己的画说明是根触点），触点之间循环这种关系直到到达根触点。当且仅当两个触点开始这个过程打到同一个根触点说明它们存在于一个连通分量中。

find()方法就是沿着这条路径找到根节点。union()方法只需将一个根节点链接到另一个上面就可实现合并分量。每个分量其实都是一个多叉树。

public int qu_find(int p) {
	while(p!=id[p]) p=id[p];
	return p;
}
	
public void qu_union(int p,int q) {
	int pRoot = qu_find(p);
	int qRoot = qu_find(q);
	if(pRoot == qRoot) return;
	id[pRoot] = qRoot;
	count--;
}

算法分析：

find()方法访问数组次数是1+触点所在树的高度*2；union()和connected()为两次。

算法改进（加权quick-union算法）：

保证小的树链接在大树上，即给每一个分量添加权重。

在类中新建一个数组保存各根节点的权重，注意该数组只有只有根结点对象的下标中的数据有效。然后修改union方法如下：

public void wei_union(int p,int q) {
	int i = qu_find(p);
	int j = qu_find(q);
	if(i == j) return;
	if(sz[i]<sz[j]) {id[i]=j;sz[j]+=sz[i]}
	else {id[j]UF = i; sz[i]+=sz[j];}
	count--;
}