code:
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.size = new Array(n).fill(1);
this.cnt = n;
}
findset(x) {
if (this.parent[x] === x) {
return x;
}
this.parent[x] = this.findset(this.parent[x]);
return this.parent[x];
}
unite(a, b) {
let x = this.findset(a);
let y = this.findset(b);
if (x === y) {
return false;
}
if (this.size[x] < this.size[y]) {
[x, y] = [y, x];
}
this.parent[y] = x;
this.size[x] += this.size[y];
this.cnt -= 1;
return true;
}
connected(a, b) {
const x = this.findset(a);
const y = this.findset(b);
return x === y;
}
}
标签:cnt,JavaScript,return,parent,查集,findset,模板,size From: https://www.cnblogs.com/fanqshun/p/17894303.html