汎用化UnionFind
UnionFindでそれぞれのグループに状態を持たせたい時用の拡張
init: 初期状態
union (x,y,rmin,rmax)
rmin, rmaxはそれぞれ root(x), root(y)の最小値, 最大値
rminにrmaxを併合する際の処理を設定する
code: GeneralUnionFind.js
class Unit {
constructor(name) { this.name = name; this.data = []; }
get(rx) { return this.datarx; }
set(x,value) { this.datax = value; return this.datax; }
set init(func) { this._init = func; }
set union(func) { this._union = func; }
get init() { return this._init; }
get union() { return this._union }
}
class UnionFind {
constructor(n, options) {
if (options == null) { options = []; }
this.units = {};
this.units'ref' = UnionFind._ref;
for (const o of options) {
if (o === 'count') { this.units'count' = UnionFind.Counter; }
else if (o instanceof Unit) { this.unitso.name = o; }
}
for (const name in this.units) {
const unit = this.unitsname;
for (let i = 0;i < n; ++i) { unit.init(i); }
}
}
root(x) {
if (this.units.ref.get(x) == x) return x;
return this.units.ref.set(x, this.root(this.units.ref.get(x)));
}
getData(name) { return this.unitsname.data; }
get(name, x) {
return this.unitsname.get(this.root(x));
}
size(x) { return this.get('count', x); }
unite(x, y) { // xとyの木を併合
const rx = this.root(x); const ry = this.root(y);
const rmax = Math.max(rx,ry); const rmin = Math.min(rx,ry);
for (const name in this.units) {
const u = this.unitsname;
u.union(x,y,rmin,rmax);
}
return true;
}
same(x, y) { // 2つのデータx, yが属する木が同じならtrueを返す
const rx = this.root(x);
const ry = this.root(y);
return rx == ry;
}
static get _ref() {
const u = new Unit('ref');
u.init = ((i) => u.datai = i);
u.union = ((x,y,rmin,rmax) => {
if (rmax == rmin) return;
u.datarmax = rmin;
});
return u;
}
static get Counter() {
const u = new Unit('count');
u.init = ((i) => u.datai = 1);
u.union = ((x,y,rmin,rmax) => {
if (rmax == rmin) return;
u.datarmin = u.datarmax + u.datarmin;
});
return u;
}
}
サンプル
ARC 037 B - バウムテスト
verified
ABC120 D
ARC037 B
Issue
Rankの管理