Dos colors P29033


Statement
 

pdf   zip

thehtml

Feu un programa que, donat un graf no dirigit, digui si és possible pintar tots els seus vèrtexs només amb dos colors, de manera que no hi hagi dos vèrtexs veïns del mateix color.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexs n i el nombre d’arestes m, seguits de 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 tot parell x y.

Sortida

Per a cada cas, escriviu “yes” si el graf és dos-colorejable, i “no” altrament.

Public test cases
  • Input

    2 1
    0 1
    
    4 3
    1 2  3 2  3 1
    
    1 0
    
    4 2
    0 3  2 1
    

    Output

    yes
    no
    yes
    yes
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python