読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

天下一2015予選A D - ハシポン

グラフ 二重辺連結成分分解

1週間かけてAC。

問題

D: ハシポン - 天下一プログラマーコンテスト2015予選A | AtCoder

連結な単純無向グラフ  G が与えられる。 G にいくつかの辺を加えた  G' が橋をちょうど1つ持つ連結な単純無向グラフとなるには、最小何本の辺を追加すればよいか? 不可能な場合その旨を答えよ。

制約

頂点数:  1 \leq V \leq 100000

辺の本数:  0 \leq E \leq 150000

与えられるグラフが連結な無向単純グラフであることは保証されている。

解法

二重辺連結成分分解というものを使います。これは強連結成分分解の無向グラフ版のようなものです。詳細はこちら↓で。

pakapa104.hatenablog.com

与えられたグラフ  G の二重辺連結成分を1つの頂点にまとめたグラフを  G_{cc} とします。 G_{cc} に存在する辺が橋の候補なので、どの辺が橋になるか全探索します。

 e = \{i, j\} をただ1つの橋とするには、頂点  i と 頂点  j の両側、 G_i,  G_j がそれぞれ1つの二重辺連結成分となるように辺を追加しなければなりません。 G_i を1つの二重辺連結成分にするために必要な最小の辺の本数は、 G_i に存在する葉(次数1の頂点)の個数を  L_i とすると、 \lfloor (L_i + 1) / 2 \rfloor です(葉を2つずつペアにして辺でつないでいけばよい)。ただし  G' が自己辺、多重辺を含んではならないという制約から、以下の場合は辺  e を最終的な橋とすることはできません。

  1.  G_i がただ1つの頂点からなり、その大きさ(1つの頂点にまとめられる前に、連結成分に属していた頂点の個数) が1
  2.  G_i がちょうど2つの頂点からなり、その大きさがともに1

あとは実装を頑張りましょう……!


(↓インデントが壊れていて申し訳ないです)

gist.github.com