abc075_c 〜グラフ上の橋を探せ〜

Quiz

https://atcoder.jp/contests/abc075/tasks/abc075_c

グラフから辺を取り除いたとき、
グラフ全体が非連結になるような辺のことを橋と呼びます。
与えられたM本のうち橋である辺の本数を求めてください。

Submit

https://atcoder.jp/contests/abc075/submissions/3908763

解き方

  • 1本エッジを削った状態で、任意のノードから開始して全部訪問できたら橋ではない
  • 制約が軽いので愚直な方法でよい

書き方

  • グラフは隣接行列で持つ。コストもないのでboolで十分
    • N<=50なのでメモリも気にならない
  • dfsで「行けるか判定」を行う
    • いつもはbfsに頼るが、あえてbfsを使ってみた
    • やってみたら、実装の重さは同じくらいだった
  • グラフを作ってから1本エッジを消すのではなく、除外するエッジを決めて、それ以外でグラフを構築しては判定した