UnionFind
code: UnionFind.js
class UnionFind {
constructor(n) {
this.ref = [];
this.count = [];
for (let i = 0;i < n; ++i) {
this.refi = i;
this.counti = 1;
}
}
root(x) {
if (this.refx == x) return x;
return this.refx = this.root(this.refx);
}
size(x) { return this.countthis.root(x); }
unite(x, y) { // xとyの木を併合
const rx = this.root(x);
const ry = this.root(y);
if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
this.refMath.max(rx,ry) = Math.min(rx,ry); //xとyの根が同じでない(=同じ木にない)時, rx,ryの小さい方を根とする
this.countMath.min(rx,ry) = this.countrx + this.country;
}
same(x, y) { // 2つのデータx, yが属する木が同じならtrueを返す
const rx = this.root(x);
const ry = this.root(y);
return rx == ry;
}
}
サンプル
ABC120 D
code: abc120_d.js
class Main {
solve() {
const nums = input.nextIntArr();
const table = input.nextIntRange(nums1);
const uf = new UnionFind(nums0);
table.reverse();
let remain = nums0 * (nums0 - 1) / 2;
const result = [];
const counts = [...Array(nums0)].map((e) => 1);
for (const node of table) {
result.push(remain);
const n = node.map(e=>e-1);
remain -= (uf.same(...n) ? 0 : (uf.size(n0) * uf.size(n1)));
uf.unite(...n);
}
console.log(result.reverse().join('\n'));
}
}