并查集 04
现实生活中，社交网络，计算机网络，如何知道两两之间是否存在联系，就是要通过并查集的方式去寻找出他们是否有根节点来确定。如果有则认为他们是有联系的，否则无。
第四版并查集
高度低的树指向高度高的树
代码
class UnionFindFour {
constructor(size) {
// parent[i]表示第i个元素所指向的父节点
this.parent = new Array(size);
// rank[i]表示以i为根的集合所表示的树的层数
this.rank = new Array(size);
// 数组个数
this.count = size;
// 初始化，每一个parent[i]指向自己，表示每一个元素自己自成一个集合
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.");
}
// 不断去查询自己的父节点，知道达到根节点
// 根节点的特点：parent[p] = p
while (p !== this.parent[p]) {
p = this.parent[p];
}
return p;
}
// 查看元素p和元素q是否所属一个集合
// O(h) 复杂度，h为树的高度
isConnected(p, q) {
return this.find(p) === this.find(q);
}
}