Please read the new rule regarding the restriction on the use of AI tools. ×

making a new undirected graph without any bridge

Revision en1, by patience, 2015-06-06 14:51:59

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.. ~~~~~ sample input: 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)