無向グラフ
重みなし無向グラフ
機能
オフセット指定
デフォルトはoffset = 1となっており、例えば辺情報が
code: input.txt
1 2
2 3
3 1
のように1-nの番号で与えられる時に内部的に1少ない値で状態を持つ
橋・連結点検出
オイラー路判定
頂点行列への変換
code: Graph.js
class Graph {
constructor() { }
from(edgeList, offset) {
if (offset === 0) {
this.edgeList = edgeList;
}
else {
if (offset == null) {offset = 1;}
this.edgeList = edgeList.map((e) =>
[e0 - offset, e1 - offset]
);
}
this.lists = [];
for (const n of this.edgeList) {
this.lists[n0]
this.lists[n0] = this.lists[n0] ? this.lists[n0] : [];
this.lists[n1] = this.lists[n1] ? this.lists[n1] : [];
this.lists[n0].push(n1);
this.lists[n1].push(n0);
}
return this;
}
isEuler () {
return this.lists.filter((list) => list.length % 2 !== 0).length <= 2;
}
isClosedEuler () {
return this.lists.every((list) => list.length % 2 === 0);
}
calcBackward() {
const used_v = [];
const used_e = [];
const ord = new Array(this.length).fill(0);
const lowlink = new Array(this.length).fill(0);
let k = 0;
const dfs = (v) => {
used_vv = true;
ordv = lowlinkv = k;
++k;
for (const _v of this.listsv) {
if (!used_v_v) {
used_ev+','+_v = true;
dfs(_v);
lowlinkv = Math.min(lowlinkv,lowlink_v);
}
else if (!used_e_v+','+v) {
// backward
lowlinkv = Math.min(lowlinkv, ord_v);
}
}
}
dfs(0);
this._lowlink = lowlink;
this._ord = ord;
this._bridges = this.edgeList.filter(e => ord[e0] < lowlink[e1]
|| ord[e1] < lowlink[e0]);
// 関節点
this._articulations = this.lists.map((list,u) => list.some((v) => ordv < ordu && ordu <= lowlinkv) || (u == 0 || list.length != 2) ? u : -1).filter(v => v >= 0);
}
get bridges() {
if (this._bridges) {return this._bridges;}
this.calcBackward();
return this._bridges;
}
get lowlink() {
if (this._lowlink) {return this._lowlink;}
this.calcBackward();
return this._lowlink;
}
get articulations() {
if (this._articulations) {return this._articulations;}
this.calcBackward();
return this._articulations;
}
get ord() {
if (this._ord) {return this._ord;}
this.calcBackward();
return this._ord;
}
get eSize() { return this.edgeList.length; }
get length() { return this.lists.length; }
get matrix() {
if (this.matrix) {return this.matrix;}
this.matrix = [];
for (let i = 0; i < this.length; ++i) {
for (let j = 0; j < this.length; ++j) {
this.matrixij = 0;
}
}
for(const e1 in this.lists) {
const l = this.listse1;
for(const e2 of l) {
this.matrixe1e2 = 1;
}
}
return this.matrix;
}
}
サンプル
橋判定
ABC075 C
code: abc075_c.js
solve() {
const size = input.nextIntArr();
const edges = input.nextIntRange(size1);
console.log(new Graph().from(edges).bridges.length);
}
Issue
オイラー路構築
有向, コスト付きグラフへの拡張