magnify

Dvidalis grafas

Pradinių duomenų failas:
dvidalis.in  
Rezultatų failas:
dvidalis.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Neorientuotasis grafas vadinamas dvidaliu, jei jo viršūnių aibę galima išskaidyti į dvi nesikertančias aibes taip, kad kiekvienos jo briaunos galai (viršūnės) priklausytų skirtingoms aibėms.

(Sąlygą galima suformuluoti ir vaizdžiau: grafas yra dvidalis, jei jo viršūnes galima nuspalvinti dviem spalvomis taip, kad jokios gretimos (sujungtos briauna) viršūnės nebūtų nuspalvintos ta pačia spalva.)

Parašykite programą, kuri nustatytų, ar duotasis grafas yra dvidalis.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašyti du sveikieji skaičiai N ir M – grafo viršūnių ir briaunų skaičiai (1 <= N <= 1000; 0 <= M <= 10 000). Grafo viršūnės sunumeruotos skaičiais nuo 1 iki N. Sekančiose M eilučių pateiktos skaičių \(u_{i}\) ir \(v_{i}\) poros (1 <= \(u_{i}\), \(v_{i}\) <= N), žyminčios, jog viršūnes \(u_{i}\) ir \(v_{i}\) grafe jungia briauna.

Rezultatai

Pirmoje rezultatų failo eilutėje turi būti įrašytas žodis TAIP, jei grafas yra dvidalis, ir žodis NE, priešingu atveju.

Pavyzdžiai

Pradiniai duomenys Rezultatai  
3 3

1 2

1 3

2 3

NE  
     
6 8

1 2

1 4

1 5

2 3

2 6

3 4

3 5

4 6

TAIP  
     
1000 0 TAIP

 

© Bronė Narkevičienė