Page 108 - REVISTA MATINF Nr. 5

˘
108 PROBLEME DE INFORMATICA PENTRU CONCURSURI

I 75 (arbori). Se d˘a un graf neorientat prin num˘arul de noduri n, num˘arul de muchii m s , i m
perechi de numere reprezentˆand extremit˘at , ile muchiilor.

Cerint , ˘a
Verificat , i dac˘a graful dat este bipartit complet s , i ˆın caz afirmativ determinat , i num˘arul de
arbori part , iali modulo 9991.

Date de intrare

Fis , ierul de intrare arbori.in cont , ine pe prima linie n si m separate printr-un spat , iu, iar
pe urm˘atoarele m linii perechi de numere separate prin cˆate un spat , iu, reprezentˆand muchiile
grafului neorientat.

Date de ies , ire

Fis , ierul de ies , ire arbori.out va cont , ine pe prima linie unul dintre cuvintele DA sau NU, ˆın
ˆ
funct , ie de situat , ia graf bipartit complet sau graf care nu este bipartit complet. In cazul ˆın care
pe prima linie s-a scris DA, atunci pe linia a doua se va scrie num˘arul de arbori part , iali modulo
9991.

Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 100

Exemplu
arbori.in arbori.out
5 6 DA
1 2 12
1 4
1 5
3 2
4 3
3 5

Timp maxim de execut , ie: 0.1 sec./test. Memorie total˘a disponibil˘a 2 MB.
Costel B˘alc˘au, Pites , ti