Xyron10's blog

By Xyron10, history, 21 month(s) ago, In English

You are given a connected undirected graph having N nodes numbered from 1 to N and M edges between its nodes. It is guaranteed that the input graph is connected and consists of no self-loops and no multiple edges between two vertices. An edge is special if it is removed then the number of connected components in the graph increases. Determine the number of unordered_pair {u, v} such that each and every Simple path (path with no edges repeated) between the node u and node v consists of exactly 1 special edge.

Can anyone help me with this problem? Thank You.

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

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The so-called special edges are the bridges in the graph which we can find in O(n + m), let's create a new graph without the bridges and count the elements in each component, then for every bridge( A — B), get the size of the component A belongs and the size of component B belongs, we add to the final result size[A] * size[B](for every node in the component of A we can pick size[B] nodes). If (a, b) and (b,a) are different answers, then we just multiply the result by 2.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share the link of the problem?