ID #123 · Colecția InfoAs · Operatori și expresii

Problema Graf bipartit

Un _graf bipartit_ (numit și _bigraf_) este un graf ale cărui vârfuri pot fi împărțite în două mulțimi disjuncte `A` și `B` (adică `A` și `B` nu au niciun vârf comun), astfel încât fiecare muchie conectează un vârf din `A` cu unul din `B` -- cu alte cuvinte, nicio muchie nu leagă două vârfuri din `A`, sau două vârfuri din `B`. ## Cerință Se dă lista muchiilor unui graf neorientat conex. Să se verifice dacă graful dat este sau nu bipartit. ## Date de intrare Programul citește de la tastatură, de pe prima linie, numerele `n` și `m`, reprezentând numărul de vârfuri, respectiv cel de muchii din graful dat, iar de pe fiecare dintre următoarele `m` linii, câte două valori `x` și `y`, cu semnificația că în graful dat există o muchie între vârfurile `x` și `y`. Valorile de pe aceeași linie sunt separate prin câte un spațiu. ## Date de ieșire Programul afișează pe ecran mesajul `DA`, dacă graful dat este bipartit, respectiv `NU` în caz contrar. ## Restricții și precizări * `1 ≤ n ≤ 100` * `1 ≤ m ≤ 100` * Pentru fiecare pereche `x, y`, `1 ≤ x, y ≤ n` * Cele `m` muchii sunt distincte