Matrix.code's blog

An odd Graph:
By Matrix.code, history, 9 years ago, In English 
You are given a undirected unweighted graph. 
Output the minimum number of edges need to be added to the graph so that , every pair of vertices has at least a even length path between them.
Imput:
A line denoting number of vertex n , and number of edges m . next m line contains the edges of the graph.
Output:
The minimum number of edges.followed by the edges

Sample input: 
3 2 
1 2
1 3
Output: 
1
2 3
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Link of the problem? and what about the constraints?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Suppose you have graph with 2 edges and 3 vertices:

1 -  > 2

2 -  > 3

You cannot satisfy condition without adding an extra vertex.. but in question , you can only add edges

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In your scenario, just adding an edge connecting vertices 1 and 3 would be enough to solve the problem. I don't think you understand the statement correctly.

    → Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Does the path need to be a simple path? If not, then you can do this:

Suppose the graph is connected. Check if it has an odd cycle. If yes, it's already good, because the cycle can change the parity of any path. If not, it's not good, because it's bipartite, and you have to add an edge to form an odd cycle.

Now the graph has k components. Check if any one of them is good. If yes, you only need k-1 edges to form a tree out of them. If not, you need k edges to form a tree and an odd cycle.

→ Reply