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本エッジを消すのではなく、除外するエッジを決めて、それ以外でグラフを構築しては判定した