并查集 05
现实生活中，社交网络，计算机网络，如何知道两两之间是否存在联系，就是要通过并查集的方式去寻找出他们是否有根节点来确定。如果有则认为他们是有联系的，否则无。
第五版并查集
路径压缩 (path compression)
代码
class UnionFindFive {
constructor(size) {
this.parent = new Array(size);
this.rank = new Array(size);
this.count = size;
for (let i = 0; i < size; i++) {
this.parent[i] = i;
this.rank[i] = 1;
}
}
// 合并元素p和元素q所属的集合
// O(h) 复杂度，h为树的高度
unionElements(p, q) {
const pRoot = this.find(p);
const qRoot = this.find(q);
if (pRoot === qRoot) {
return;
}
// 根据两个元素所在树的元素个数不同判断合并方向
// 将元素个数少的集合合并到元素个数多的集合上
if (this.rank[pRoot] < this.rank[qRoot]) {
this.parent[pRoot] = qRoot;
} else if (this.rank[qRoot] < this.rank[pRoot]) {
this.parent[qRoot] = pRoot;
} else {
this.parent[pRoot] = qRoot;
// 维护rank的值
this.rank[qRoot] += 1;
}
}
// 查看过程，查找元素p所对应的集合编号
// O(h) 复杂度，h为树的高度
find(p) {
if (p < 0 || p >= this.count) {
throw new Error("index out of bound.");
}
// 路径压缩版本1
while (p !== this.parent[p]) {
this.parent[p] = this.parent[this.parent[p]];
p = this.parent[p];
}
return p;
// 路径压缩版本2
// if (p !== this.parent[p]) {
// this.parent[p] = this.find(this.parent[p]);
// }
// return this.parent[p];
}
// 查看元素p和元素q是否所属一个集合
// O(h) 复杂度，h为树的高度
isConnected(p, q) {
return this.find(p) === this.find(q);
}
}