-
Notifications
You must be signed in to change notification settings - Fork 0
/
weightedQuickUnion.js
54 lines (44 loc) · 1.19 KB
/
weightedQuickUnion.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
Weighted Quick Union + Path Compression
O(N + M lg* N)
*/
function WeightedQuickUnion (size) {
this.id = [];
this.size = [];
for (var i = 0; i < size; i++) {
this.id[i] = i;
this.size[i] = 1;
}
}
WeightedQuickUnion.prototype.union = function (a, b) {
var aRoot = this.root(a),
bRoot = this.root(b);
if (aRoot === bRoot) {
return;
}
if (this.size[aRoot] < this.size[bRoot]) {
this.id[aRoot] = bRoot;
this.size[bRoot] += this.size[aRoot];
} else {
this.id[bRoot] = aRoot;
this.size[aRoot] += this.size[bRoot];
}
};
WeightedQuickUnion.prototype.root = function (a) {
while (a != this.id[a]) {
this.id[a] = this.id[this.id[a]];
a = this.id[a];
}
return a;
};
WeightedQuickUnion.prototype.connected = function (a, b) {
return this.root(a) === this.root(b);
};
var wqu = new WeightedQuickUnion(10);
wqu.union(0, 1);
wqu.union(5, 6);
wqu.union(6, 7);
console.log('wqu.connected(5, 7)', wqu.connected(5, 7)); // true
console.log('wqu.connected(0, 7)', wqu.connected(0, 7)); // false
wqu.union(5, 1);
console.log('wqu.connected(0, 7)', wqu.connected(0, 7)); // true