-
Notifications
You must be signed in to change notification settings - Fork 10
/
UnionFind.ts
52 lines (41 loc) · 1.1 KB
/
UnionFind.ts
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
export default class UnionFind {
private ranks: number[];
private connections: number[];
constructor(size: number) {
this.connections = [...Array(size).keys()];
this.ranks = [...Array(size).keys()];
}
public union(x: number, y: number) {
let xRoot = this.find(x);
let yRoot = this.find(y);
if (xRoot === yRoot) {
return;
}
if (this.ranks[xRoot] < this.ranks[yRoot]) {
[xRoot, yRoot] = [yRoot, xRoot];
}
this.connections[yRoot] = xRoot;
if (this.ranks[xRoot] === this.ranks[yRoot]) {
this.ranks[xRoot] += 1;
}
}
public find(val: number) {
if (this.connections[val] !== val) {
this.connections[val] = this.find(this.connections[val]);
}
return this.connections[val];
}
public getClusters() {
const result = {};
for (const [index, connection] of this.connections.entries()) {
if (index === connection) {
result[index] = new Set();
}
}
for (const index of this.connections.keys()) {
const cluster = this.find(index);
result[cluster].add(index);
}
return result;
}
}