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
Link of the problem? and what about the constraints?
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
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.
thanks I get it now, by joining 1,3 we get path from 1-3-2 which is 2 length (even)
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.