1class UnionFind {
2 constructor(n) {
3 this.parent = Array.from({length: n}, (_, i) => i);
4 this.rank = new Array(n).fill(0);
5 }
6 find(x) {
7 while (this.parent[x] !== x) x = this.parent[x];
8 return x;
9 }
10 union(a, b) {
11 const ra = this.find(a), rb = this.find(b);
12 if (ra === rb) return;
13 if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
14 else { this.parent[rb] = ra; if (this.rank[ra] === this.rank[rb]) this.rank[ra]++; }
15 }
16}