# AtCoder Beginner Contest 075

URL: https://atcoder.jp/contests/abc075 (opens new window)

# C

require "set"
n,m = gets.chomp.split(" ").map(&:to_i)
ab_arr = m.times.map{gets.chomp.split(" ").map(&:to_i)}

hash = {}
edge = []
# 無向グラフを作成
ab_arr.each do |(a, b)|
  hash[a] ||= []
  hash[a] << b
  hash[b] ||= []
  hash[b] << a
  # 辺は小さい順に並べたほうが都合が良い(a == bはあり得ないので考慮しなくてOK)
  edge << [a, b] if a < b
  edge << [b, a] if b < a
end

count = 0
# 各辺を取り除いたときに, 全頂点がたどれるかを確認
edge.each do |(e_a, e_b)|
  bfs = [1]
  node_set = Set.new([1])
  edge_set = Set.new
  while bfs.length > 0 do
    a = bfs.shift
    hash[a].each do |b|
      # 小さい順に並べたほうが都合が良い
      in_a, in_b = a, b if a < b
      in_a, in_b = b, a if b < a
      # 通れない辺
      next if e_a == in_a && e_b == in_b
      # すでに通った辺
      next if edge_set.include?([in_a, in_b])
      bfs << b
      node_set << b
      edge_set << [in_a, in_b]
    end
  end
  # 全頂点通れないなら橋としてカウント
  count += 1 if node_set.length != n
end

puts count
Last Updated: 2020/08/18 23:38