Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя Matrix.code

An odd Graph:
Автор Matrix.code, история, 9 лет назад, По-английски 
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
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Link of the problem? and what about the constraints?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

→ Ответить