并查集快速查找
最后更新于：2022-03-27 02:54:05
并查集快速查找
本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。
查询元素所在的集合编号，直接返回 id 数组值，O(1) 的时间复杂度。
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
…
合并元素 p 和元素 q 所属的集合， 合并过程需要遍历一遍所有元素, 再将两个元素的所属集合编号合并，这个过程是 O(n) 复杂度。
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
…
Java 实例代码
源码包下载：Download
UnionFind1.java 文件代码：
/**
* 第一版union-Find
*/
public class UnionFind1 {
// 我们的第一版Union-Find本质就是一个数组
private int[] id;
// 数据个数
private int count;
public UnionFind1(int n) {
count = n;
id = new int[n];
// 初始化, 每一个id[i]指向自己, 没有合并的元素
for (int i = 0; i < n; i++)
id[i] = i;
}
// 查找过程, 查找元素p所对应的集合编号
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
// 查看元素p和元素q是否所属一个集合
// O(1)复杂度
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
// 合并元素p和元素q所属的集合
// O(n) 复杂度
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
}