View on GitHub

cp-library

Biconnected Components ( 2-連結成分 )

C++ 用ライブラリ一覧に戻る

ソースコード

nachia/graph/biconnected-components.hpp

主な機能

自己ループを持たない無向グラフを $2$-連結成分に分解して、その成分に番号を振る。

グラフが $2$-連結であるとは、そのグラフが連結であり、さらに $1$ つどの頂点を選んで(その頂点とそれに隣接するすべての辺を)取り除いても連結であることである。無向グラフの $2$-連結成分とは $2$-連結な部分グラフのうち極大なものである。

孤立点は $1$ つの $2$-連結成分である。グラフの各辺は、ちょうど $1$ つの $2$-連結成分に属する。

再帰の深い関数を使わない。

struct BiconnectedComponents

コンストラクタ

BiconnectedComponents(Graph G = Graph(0, true));

nachia::Graph とは?

メインの計算を行う。

numComponents

int numComponents() const;

$2$-連結成分の個数を返す。

getBcVertices

CsrArray<int> getBcVertices() const;

各 $2$-連結成分の頂点集合を返す。頂点の番号は与えられたグラフのものである。

getBcEdges

CsrArray<int> getBcEdges() const;

各 $2$-連結成分の辺の番号の集合を返す。辺の番号は与えられたグラフのものである。

getBcTree

CsrArray<int> getBcTree() const;

無向森 block-cut tree (?) の隣接リスト表現を返す。(与えられるグラフが連結でない場合、出力は木でないかもしれない。)

$n$ 個の頂点は頂点 $0$ から $n-1$ ( cut node )にそのまま対応し、 $i$ 番目の $2$-連結成分が頂点 $n+i$ ( block node )に対応する。

block node に隣接する cut node の集合は、 $2$-連結成分に属する頂点集合に一致する。

参考


TOP PAGE