Màxim nombre de vèrtexs vermells P24562


Statement
 

pdf   zip

thehtml

Feu un programa que, donat un graf no dirigit, digui si és possible pintar-ne tots els vèrtexs només amb dos colors (vermell i blau), de manera que no hi hagi dos vèrtexs veïns del mateix color. En cas afirmatiu, cal maximitzar el nombre de vèrtexs de color vermell.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexs n i el nombre d’arestes m, seguits d’m parells x y indicant una aresta entre x i y. Suposeu 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, que els vèrtexs es numeren entre 0 i n − 1, xy, i que no hi ha més d’una aresta entre cada parell x y.

Sortida

Per a cada cas, si el graf es pot pintar amb els dos colors, escriviu “yes” seguit del màxim nombre possible de vèrtexs vermells. Altrament, escriviu “no”.

Public test cases
  • Input

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

    Output

    yes 1
    no
    yes 1
    yes 4
    yes 5
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++