ゆらのふなびと

競プロ, Python, C++

二重辺連結成分分解 ライブラリ

二重辺連結成分分解のライブラリと、アルゴリズムの概説です。

この記事ではimos法を使った方法でやっています(恐らくこっちの方が初学者にはわかりやすい)。


二重辺連結成分とは、「その成分に含まれるどの1辺を除いても、その成分が非連結にならないような部分グラフ」のことです。

という言葉を定義すると、二重辺連結成分とは、「すべての橋をグラフから取り除いたときの連結成分」であると言うこともできます。橋とは、その1辺を取り除いただけでグラフが非連結となるような辺のことです。よって橋を列挙することができれば、二重辺連結成分も列挙することができます。

橋の列挙にはimos法が使えます。↓のDの解説の図がわかりやすいです。

www.slideshare.net

ざっくり言うと、まずグラフに対してDFS木を作ります。すると、このDFS木上の辺で、後退辺(DFS木に使われなかった辺)により被覆されない辺が橋になります。橋であれば必ずDFS木に含まれるので、後退辺が橋の候補となることはありません。DFS木に使われなかった辺  e = \{a, b\} は必ず、 a bLCA a, b のどちらかとなるように張られています。そこで  a, b のうち親から遠い方を  a とすると、 imos[edge\{a, par(a)\}]++, imos[edge\{b, par(b)\}]-- という前処理をして後で根に向けて累積和を取ることにより、DFS木上の各辺が後退辺に被覆される回数を求めることができます。

橋を列挙できたら、あとは橋以外の辺のみを用いて各頂点からDFSして、連結成分番号を振っていけばOKです。

ちなみに、二重辺連結成分を1つの頂点にまとめたグラフは木になります*1。これが分かっているとあとの処理が楽になりそうです。

以下のコード、辺についてのループで毎回4行くらいとっているのがかっこ悪いですね。何かいい方法はないでしょうか……。

実用例はこちら↓

pakapa104.hatenablog.com

gist.github.com

*1:理由を直観的に説明すると、二重辺連結成分分解がいわば強連結成分分解の無向グラフ版であること、強連結成分分解を1つの頂点にまとめたグラフがDAGになることからイメージはつきそうです