Minimize the number of bridges on the chart

Question

I tried to solve the problem, which basically boils down to the following:
Give a set of nodes N with numbers from 1 to N and M , where N <10000 and M <100000 ,
Find Edge (u, v) , which when added to the graph - Minimizes the number bridges in the graph .
If there are many such ribs - print one that has low lexicographical value.
What will be an effective approach to this problem?

Answer 1

I think this problem is very complex. Here I would describe a solution that I can think of:

1) Find all the bridges in the schedule.

2) Now imagine that bridges are the only edges you want on your schedule. You save bridges and connect all nodes between bridges in large nodes.

3) Now you have a tree. Edges are bridges, nodes are "large nodes" that combine nodes from the previous graph.

4) Call this forest count T.

5) Connecting any two nodes in column T creates a loop. Any edge in the cycle is not a bridge.

6) Point 5 implies that a solution is found by creating the longest cycle. You can do this simply by finding the two nodes with the longest distance between them.

7) . : ?

, - .