Archipiélago P31958


Statement
 

pdf   zip

thehtml

Un archipiélago está constituído por n islas, algunas de las cuales están conectadas por puentes bidireccionales. Se sabe que hay como mucho un camino entre cada par de islas. Se ‍quieren construir hospitales de manera que nadie tenga que cruzar más de un puente para llegar a un hospital. ¿Cuál es el mínimo número de hospitales necesarios?

Entrada

La entrada consiste en varios casos, cada uno con n y el número de puentes p, seguidos de p pares x y, con xy, con las islas conectadas por cada puente. Suponed 1 ≤ n ≤ 105, 0 ≤ p < n, que las islas se numeran desde 0, y que no hay más de un puente entre dos islas.

Salida

Para cada caso, escribid el mínimo número de hospitales.

Puntuación

  • Test-1:  ‍ Entradas con n ≤ 8.  ‍18 Puntos ‍
  • Test-2:  ‍ Entradas con n ≤ 100.  ‍27 Puntos ‍
  • Test-3:  ‍ Entradas de todo tipo.  ‍55 Puntos ‍
Public test cases
  • Input

    10 6
    0 1
    3 4
    4 5
    6 7
    7 8
    8 9
    
    9 8
    0 4
    7 0
    3 5
    8 6
    1 6
    2 8
    4 1
    5 1
    
    5 4
    0 2
    2 1
    1 3
    1 4
    

    Output

    5
    3
    2
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++