2015 ACM Amman Collegiate Programming Contest ( H.Bridge)

Problem link: H. Bridges

Idea: 

 First, find all bridges in the given graph, then remove them from the graph and find all components of the resulting graph.

Consider each component as a single vertex and add the bridges again, now you have a tree where all edges are bridges (in the original graph).
In the resulting tree, to make an edge not a bridge, it has to be in a cycle, and since all edges in this cycle won't become bridges anymore, you have to create the largest possible cycle, so find the longest path in the tree, and connect it's endpoints. Final answer is : Total number of bridges — length of resulting cycle + 1
Which is equal to : Total number of bridges — longest path in tree.

 

Share: