making a new undirected graph without any bridge

Revision en2, by patience, 2015-06-06 14:54:01

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English patience 2015-06-06 14:54:01 47
en1 English patience 2015-06-06 14:51:59 733 Initial revision (published)