一 代码
package common;
/**
* @className: QuickUnionUF
* @description: 动态连通性问题的quick-union算法实现
* @date: 2021/2/25
* @author: cakin
*/
public class QuickUnionUF {
private int[] parent; // 分量id
private int count; // number of components
/**
* 功能描述：初始化触点
*
* @param n 触点个数
* @author cakin
* @date 2021/2/25
*/
public QuickUnionUF(int n) {
// 初始化分量parent数组
parent = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
/**
* 功能描述：连通分量的数量
*
* @return int 连通分量的数量
* @author cakin
* @date 2021/2/25
*/
public int count() {
return count;
}
/**
* 功能描述：p触点所在的连通分量
*
* @param p p触点
* @return int 触点所在的连通分量
* @author cakin
* @date 2021/2/25
*/
public int find(int p) {
validate(p);
while (p != parent[p])
p = parent[p];
return p;
}
/**
* 功能描述：判断p触点是否有效
*
* @param p p触点
* @author cakin
* @date 2021/2/24
*/
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n - 1));
}
}
/**
* 功能描述：判断p触点和q触点是否连通
*
* @param p 第1个触点
* @param q 第2个触点
* @return boolean 是否连通
* @author cakin
* @date 2021/2/25
*/
@Deprecated
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/**
* 功能描述：在p和q之间添加一条连接
*
* @param p 第1个触点
* @param q 第2个触点
* @author cakin
* @date 2021/2/24
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// 将触点p和触点q的根节点统一
parent[rootP] = rootQ;
count--;
}
/**
* 功能描述：quick-union算法测试
*
* @param args 命令行
* @author cakin
* @date 2021/2/25
*/
public static void main(String[] args) {
// 读取触点数量
int n = StdIn.readInt();
// 初始化N个分量
QuickUnionUF uf = new QuickUnionUF(n);
while (!StdIn.isEmpty()) {
// 读取整数对
int p = StdIn.readInt();
int q = StdIn.readInt();
// 如果已经连通，则忽略
if (uf.find(p) == uf.find(q)) {
continue;
}
// 归并分量
uf.union(p, q);
// 打印连接
StdOut.println(p + " " + q);
}
// 打印分量数量
StdOut.println(uf.count() + " components");
}
}二 测试
F:\Algorithm\target\classes>java common.QuickFindUF < tinyUF.txt
4 3
3 8
6 5
9 4
2 1
5 0
7 2
6 1
2 components三 说明
quick-union算法是quick-find算法的一种改良，大多数情况下quick-union性能强于quick-find。