1class UnionFind {
2 constructor(n) {
3 this.parent = Array(n).fill(0).map((_, i) => i);
4 this.rank = Array(n).fill(0);
5 }
6
7 find(x) {
8 if (this.parent[x] !== x) {
9 this.parent[x] = this.find(this.parent[x]); // compress
10 }
11 return this.parent[x];
12 }
13
14 union(x, y) {
15 const rx = this.find(x), ry = this.find(y);
16 if (rx === ry) return;
17 if (this.rank[rx] < this.rank[ry]) {
18 this.parent[rx] = ry;
19 } else if (this.rank[rx] > this.rank[ry]) {
20 this.parent[ry] = rx;
21 } else {
22 this.parent[ry] = rx;
23 this.rank[rx]++;
24 }
25 }
26
27 connected(x, y) {
28 return this.find(x) === this.find(y);
29 }
30}