解决方案 - 遍历所有边,并计算偶数边的数量
如果我们从树中删除一条边,它会导致两棵树的顶点数为偶数,我们称该边为偶数边
如果我们从树中删除一条边并导致两棵树的顶点数为奇数,我们称该边为奇数边
这是我在 Ruby 中的解决方案
num_vertices, num_edges = gets.chomp.split(' ').map { |e| e.to_i }
graph = Graph.new
(1..num_vertices).to_a.each do |vertex|
graph.add_node_by_val(vertex)
end
num_edges.times do |edge|
first, second = gets.chomp.split(' ').map { |e| e.to_i }
graph.add_edge_by_val(first, second, 0, false)
end
even_edges = 0
graph.edges.each do |edge|
dup = graph.deep_dup
first_tree = nil
second_tree = nil
subject_edge = nil
dup.edges.each do |e|
if e.first.value == edge.first.value && e.second.value == edge.second.value
subject_edge = e
first_tree = e.first
second_tree = e.second
end
end
dup.remove_edge(subject_edge)
if first_tree.size.even? && second_tree.size.even?
even_edges += 1
end
end
puts even_edges
注意 -单击此处查看 Graph、Node 和 Edge 类的代码