动态连通性问题中，如何判断触点是否相连接，可以抽象表述为如何编写程序来过滤掉序列中所有无意义的整数对。
连通性问题只要求我们的程序能够判定给定的整数对p，q是否相连接，但并不要求给出两者之间通路上的所有连接，反而加大了问题的难度。为了简化说明问题，我们不妨自己设计一份API来封装所需要的操作：初始化，连接两个触点，判断包含某两个触点的分量，判断两个触点是否在同一个分量，返回所有分量的数量。
通过自己定义如何连接，我们可以很容易的判断是否连接。
public class UF{
private int[] id;
private int count;
public UF(int N){
count = N;
id = new int[N];
for(int i = 0; i < N; i++)
id[i] = i;
}
public int count(){
return count;
}
public boolean connected(int p, int q){
return find(p) == find(q);
}
public int find(int p)
public int union(int p, int q)
public static void main(String[] args){
int N = StdIn.readInt();
UF uf = new UF(N);
while(!StdIn.isEmpty()){
int p = StdIn.readInt();
int q = StdIn.readInt();
if(uf.connected(p, q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
}
}
上述代码实现了基本的API，还剩下union和find两个函数没有实现。下面来看几种不同的解决方案。
- quick-find
private int find(int p){
return id[p];
}
public void union(int p, int q){
int pID = find(p);
int qID = find(q);
if(pID == qID) return;
for( int i=0; i<id; i++)
if( id[i] == pID) id[i] = qID;
count--;
}
quick-find算法中，find()操作只需要访问数组一次，但是每一次归并两个分量的union()操作需要访问数组(N+3)(2N+1)次。假使我们使用quick-find算法解决连通性问题并最终只剩下一个分量，至少需要调用N-1次的union()，即至少(N+3)(N-1)N²次数组访问。
- quick-union
private int find(int p){
while( p != id[p]) p=id[p];
return p;
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
quick-union算法将会把触点连接成为一棵树，我们定义一棵树的大小为节点的数量，树中一个节点的深度是它到根节点路径上的链接数，树的高度是它最大的深度。
那么quick-union算法中的find()方法访问数组的次数为1加上给定触点所对应节点深度的两倍。union()方法访问数组的次数为两次find()操作（如果union()中两个触点位于不同的分量中还要再加1）。
- weighted-quick-union
我们很容易发现quick-union算法在最坏的情况下，仍然是平方级别的，此时形成的树没有分岔。我们可以简单的修改从而避免这一情况。quick-union中随意将一棵树连接至另一棵树，现在我们记录每一颗树的大小以确保将小树连接在大树上。
public class weightedQuickUnionUF{
private int[] id;
private int[] sz;
private int count;
public WeightedQuickUnionUF(int N){
count = N;
id = new int[N];
for(int i=0; i<N; i++) id[i] = i;
sz = new int[N];
for(int i=0; i<N; i++) id[i] = 1;
}
public int count(){
return count;
}
public boolean connected(int p, int q){
return find(p) == find(q);
}
private int find(int p){
while( p != id[p]) p = id[p];
return p;
}
public void union(int p, int q){
int i = find(p);
int j = find(q);
if( i == j) return;
if( sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i];}
else { id[j] = i; sz[i] += sz[j]; }
count--;
}
}