documentation_of
//graph/others/namori-graph.hpp

概要

$n$ 頂点 $n$ 辺からなる連結無向グラフは, サイクルが $1$ 個だけあるグラフとなる。

このグラフを, とある漫画家のアイコンにちなんでなもりグラフと呼ばれることがるが, 学術的には Unicyclic Graph, Pseudoforest が正しい。

ここでは, このグラフを 1 つのサイクルと, サイクル内の頂点に付属する木に分解する。またサイクルに含まれる頂点番号を, サイクルの頂点数を $k$ として $[0, k)$ にふりなおし, これを tree_id と呼ぶことにする。

また付属する木も同様に, 木の頂点数を $l$ として $[0, l)$ にふりなおす。

使い方

build(): サイクルと木に分解する。頂点数と辺の本数が同じ無向連結グラフである必要がある。
forest: 分解した無向木が tree_id の昇順に格納される。木の頂点番号は$0$ から振り直している。辺の from, to は振り直し後の頂点番号, cost,idx はもとのグラフの辺の値をコピーする。
loop_edges: サイクルに含まれる辺が順に格納される。$i$ 番目の辺は tree_id $i$ と $i+1$ を結ぶ辺である。辺の from, to, cost, idx はもとのグラフの辺の値をコピーする。
operator[k]: 頂点 $k$ について, サイクルの tree_id, 振り直された木の頂点番号 id を返す。
inv(tree_id, k): サイクルの tree_id に付属する頂点 $k$ のもとの頂点番号を返す。特に inv(tree_id, 0) はサイクルに含まれていたもとの頂点番号を指す。