橋・二重辺連結成分分解
この記事は、Competitive Programming Advent Calendar 2016の記事……ではなく、僕のAdCの記事を楽しむための予備知識として書かれた記事です。
ちなみに、僕の担当は明後日です。よろしくおねがいします。
グラフ上の「橋*1」となる辺を求め、これによりグラフを複数の「二重辺連結成分*2」に分解する方法を解説します。
補足を注釈に書いていたりするので、適宜参照して下さい。
アルゴリズム
前置き
橋は、imos法を用いた方法*3やlowlinkを使う方法*4で列挙することができ、橋を取り除いたグラフでDFSをすることで二重辺連結成分に分解できます。
一方ここでは、Spaghetti Sourceのコードに基づいた、DFSをしながら橋と二重辺連結成分をまとめて列挙する方法を解説します。
以下の説明では「DFS木」や「後退辺」といった用語の説明は省きます。
その辺りの知識が不安な場合、npcaの部誌(2014)のP25あたりを読むと良いと思います。(ちなみに、この部誌ではlowlinkを使った橋の列挙方法を解説しています。)
実装
「アルゴリズム」の章では大まかな動作を解説しました。ここでは、具体的な実装を解説します。
はじめに、使用するデータ構造についての解説を以下に示します。
型 | 変数名 | 説明 |
---|---|---|
vector<int> | order | 各頂点に訪れた順番 |
stack<int> | S | 既に訪れた頂点のうち、まだどの二重辺連結成分にも割り振られていない頂点の集合 |
vector<bool> | inS | 集合Sに各頂点が含まれているかどうかの情報 |
stack<int> | roots | 各二重辺連結成分を、DFS木の部分木として見た時の根の集合 |
適当な頂点を根としてDFSを開始します。
以下の解説では、現在訪れている頂点をcurと呼び、一つ前に訪れた頂点をprevと呼びます。
新しい頂点を訪れる度に以下の動作を行います。
- order[cur]にorder[prev]+1を代入することで、その頂点に訪れた順番を記録
- 集合Sにcurを追加し、curを追加したことをinSに記録
- rootsにcurを追加
使おうとした辺(cur,to)が後退辺である場合(つまり「to!=prev && inS[to]」の場合 )、以下の動作を行います。
- cur〜toまでの頂点(ただしtoは含まない)をrootsから捨てる
roots.top()の頂点より葉側の頂点の訪問が終了した場合(つまり「cur==roots.top()」の場合)、以下の動作を行います。
なお説明のため、roots.top()の頂点を以下ではnodeと呼びます。
- nodeと、DFS木上でnodeより1つだけ根側にある頂点を橋として記録する(nodeが根である場合はなにもしない)
- 一度目にnodeに訪問してから、nodeに戻ってくるまでに訪問した頂点をすべて同じ連結成分分解として記録する。(S.top()がnodeで無い間、topの値を記録し続けることで実現できる。)
- rootsのtopの格納されている頂点をpopする
上記の動作を行うことによって最終的に、bridge関数の引数であるbrgに橋のリストが、each_bccに二重連結成分のリストが、cmpにある頂点がどの二重連結成分に含まれているかの情報が格納される。