patience's blog

By patience, history, 9 years ago, In English

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

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by patience (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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