🌳
[ABC075 C] Bridge
辺を削除して木の数を求める問題。
問題を簡潔にする
グラフから辺を取り除いたとき、グラフ全体が非連結になるような辺のことを橋と呼びます。
与えられた M 本のうち橋である辺の本数を求めてください。
を、
- 一本の木から幹を外すと複数の木になってしまうケースは何個ある？
に言い換える。
このようにいくら読んでも頭に入って来ない文章は都合のいいように校正する。
幹は外せない
ただし、素集合データ構造は幹を外せないので、最初から外したい幹を使わずに作る。その上で、二つ以上の木になったケースをカウントする。
現実の問題に言い換える
- 橋が多すぎるので減らしたいが行けない場所がないようにしたい
と言い換えることもできる。この場合、橋を減らしたことで行けない場所がでてきてしまったら、その橋は必要だったということ。現実であればその「残すべき橋」が重要だと思われるが、問いではその数だけが求められている。
コード
N, M = gets.split.collect(&:to_i) # => [7, 7]
AB = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 3], [2, 7], [3, 4], [4, 5], [4, 6], [5, 6], [6, 7]]
count = AB.each_index.count do |skip|
edges = AB.reject.with_index { |_, i| i == skip }
DisjointSet.new(1..N).unites(edges).tree_count >= 2
end
p count # => 4
Discussion