GRL_3_A: Articulation Point

関節点を列挙する
関節点とは、そこを削除するとグラフが非連結になる点

頂点をひとつずつ選んで削除して連結かどうか確かめる、
っていうのなら既出のアルゴリズムでループ回すだけだけど
さすがにそれは面白くなさすぎる

ヒントのアイコンは深さ優先探索
ヒントの図はまだ意味が読み取れない

今までやったアルゴリズムで関係ありそうなのはあるだろうか
連結成分分解は関係が深そうだし
全部の点をいっぺんに、というと全点対間最短経路とか
でも直接応用する方法は思いつかない

グラフのアルゴリズムでは、1点から始めてひとつずつ点を追加していく
やり方と、いっぺんに全体を処理するやり方があった
この問題はどっちがいいか

ふむ
そこを削除するとグラフが非連結になる点というのはどんな点なのか、から
あらためて考えてみる必要がありそう
全体を見れば一目瞭然だけれども、コンピュータの視点では

ループの一部になっている、というのは言い換えたことになっているだろうか
確かにそうだろうけどコンピュータで効率良く処理できる？
すべてのループを確かめました、これだけやって見つからなかったんだから
ほかには絶対ありません、って言えるまでがんばるのは大変そうだなあ

頂点をひとつずつ選んで削除して連結かどうか確かめる、でも
過去の計算をうまく再利用できればいいのかもしれない
頂点を削除するってことになってるけど辺を削除するって考えたほうが
シンプルになりそうな気もする・・・けどダメか
ヒントの図に引きずられたけど、橋みたいになってる辺がなくっても
関節点になることはあるし、辺を取るのと頂点を取るのでは結果が違う

深さ優先探索ありきで考えてみるか
探索していって探索済みの頂点にぶつかった、つまりループした経路が
見つかったらそのループ上の頂点を除外していき、
全経路を探索し終わるまで探索を続ける、をやってみよう
すべてのループを確かめましたにはならないけど、なんていうのかな
必要な分のループを確かめました、にはなるかも

でいったん書いてみた
だめだった
なんでもいいからループの一部ならいいってわけじゃないもんな

えー難しいですー