Given an undirected graph with N nodes and M edges. The score of the graph is the number of good edge which we can collect. A good edge is a edge which is not a part of a cycle. Now John wants to add exactly one edge to this graph in such a way that the number of good edges is as minimum as possible.
Example -
5 4 ->n,m (1 2), (1 3), (1 4), (1 5)
Initially, there are a total of '4' good edges . One of the best ways to reduce the number is by adding edge between '2' and '5'. Now, there are only '2' good edges (1 → 3 and 1 → 4) which can be used. So, the answer is '2'.
Are we collecting nodes or edges? The original graph has 4 edges and 5 nodes not part of any cycle.
we are collecting edges, sorry corrected the statement
Definition: An edge which is not part of any simple cycle is called a bridge.
We want to maximize the number of bridges we can turn into non-bridges.
Take the original graph and compress any two nodes connected by a non-bridge into a single node. The remaining graph will be the bridge tree of the original graph.
Because the bridge tree is a tree and not any graph, the following holds:
If we were to connect two nodes with a new edge, all bridges on the paths between them would get turned into non-bridges but no other edges would be effected. Thus, we need to find the maximum number of bridges between any two nodes, which is equal to the diameter of the bridge tree.
Thus, the answer is $$$(\text{number of bridges}) - (\text{diameter of bridge tree})$$$.
Time complexity is $$$O(V + E)$$$ when implemented properly.