并查集 03
现实生活中，社交网络，计算机网络，如何知道两两之间是否存在联系，就是要通过并查集的方式去寻找出他们是否有根节点来确定。如果有则认为他们是有联系的，否则无。
第三版并查集
使用节点个数少的节点指向节点个数多的节点
缩减查看时间，合理进行union操作
代码
class UnionFindThree {
constructor(size) {
// 每个元素对应的父节点
this.parent = new Array(size);
// 元素个数（节点数量）
this.branch = new Array(size);
this.count = size;
// 初始化
for (let i = 0; i < size; i++) {
this.parent[i] = i;
this.branch[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.branch[pRoot] < this.branch[qRoot]) {
this.parent[pRoot] = qRoot;
this.branch[qRoot] += this.branch[pRoot];
} else {
this.parent[qRoot] = pRoot;
this.branch[pRoot] += this.branch[qRoot];
}
}
// 查看过程，查找元素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);
}
}