let's consider a initial graph.. this graph may contain bridge(one or more) or not.. now my task is to if this graph contain bridge i have to add some new edge so that resultant graph does not contain any. bridge..but the number of new edge as small as possible..
n=number of node
m=number of edge initial graph
n=4 m=3
1 2
2 3
2 0
n=3 m=3
1 2
2 0
0 1
output:
Case 1: 2
Case 2: 0
how can i solve this problem using articulation point(bridge) algorithm?? problem link:http://lightoj.com/volume_showproblem.php?problem=1291 thanks in advance
Auto comment: topic has been updated by patience (previous revision, new revision, compare).
every group of nodes that can reach each other without passing through a bridge call it a component.
replace every component with a single node , if there's a bridge connecting two components then make an edge between the two corresponding nodes, now your graph is tree and your problem is to find minimum path edge-cover in this tree