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 とは？

• 頂点数： $1 \leq n \leq 1 \times 10^7$
• 辺数： $1 \leq m \leq 1 \times 10^7$
• $G$ は自己ループを含まない無向グラフ。
• $O(n + m)$ 時間

メインの計算を行う。

numComponents

int numComponents() const;

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

getBcVertices

CsrArray<int> getBcVertices() const;

• $O(n + m)$ 時間

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

getBcEdges

CsrArray<int> getBcEdges() const;

• $O(n + m)$ 時間

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

getBcTree

CsrArray<int> getBcTree() const;

• $O(n + m)$ 時間

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

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

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

参考

• コラム 非再帰DFS link

---

TOP PAGE