650iq's blog

By 650iq, 6 months ago, In English

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'.

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are we collecting nodes or edges? The original graph has 4 edges and 5 nodes not part of any cycle.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    we are collecting edges, sorry corrected the statement

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

  • For any two nodes, all simple paths between them go through the same set of bridges, which is the set of bridges in the bridge tree on the path between the nodes' components.

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had observed that part that we need to remove the diameter but didn't had idea about how to find the bridge tree. Thanks a lot. Ill try to implement this