Page 128 - MATINF Nr. 9-10

˘
128 PROBLEME DE INFORMATICA PENTRU CONCURSURI

a
I 132 (greuler). Se d˘ un graf neorientat conex prin num˘arul de noduri n, num˘arul de muchii
m s , i perechile de noduri ce reprezint˘a muchiile. Se cere s˘a se determine num˘arul minim de
a
a
muchii NrMin ce trebuie ad˘augate la graful dat pentru ca acesta s˘ devin˘ graf eulerian, dac˘
a
ˆ
a
acest lucru este posibil. In caz contrar se consider˘ c˘ NrMin = −1.
a
Restrict , ii s , i preciz˘ari
• 1 ≤ n ≤ 50;
• Pentru toate testele, graful este conex.

Date de intrare

a
Fis , ierul greuler.in cont , ine pe prima linie n s , i m separate prin spat , iu s , i pe urm˘toarele m
linii perechi de noduri (separate prin cˆate un spat , iu) ce reprezint˘a muchiile grafului.
Date de ie¸sire

Fis , ierul de ies , ire greuler.out va cont , ine pe prima linie num˘arul NrMin cerut ˆın enunt , .
Exemplu

greuler.in greuler.out Explicat , ie
5 4 1 Graful nu este eulerian,
2 4 iar prin ad˘augarea muchiei
5 2 [1, 3] devine eulerian.
3 2
1 2

Timp maxim de execut , ie: 1 secund˘a/test.
a
a
Memorie total˘ disponibil˘ 2 MB.
Costel B˘alc˘au, Pites , ti
a
I 133 (conex3). Se d˘ un graf neorientat conex cu n noduri s , i m muchii. Pentru acest graf se
dores , te determinarea a dou˘a muchii, care dac˘a se elimin˘a se obt , ine un graf cu 3 componente
conexe.

a
Cerint , ˘
a
Cunoscˆand n, m s , i cele m muchii, se cere s˘ se determine dou˘ muchii, care dac˘ se elimin˘
a
a
a
conduc la un graf cu 3 componente conexe.
Restrict , ii s , i preciz˘ari
• 1 ≤ n ≤ 50;

• Pentru toate testele din fis , ierul de intrare exist˘ solut , ie!
a

Date de intrare
Fis , ierul conex3.in cont , ine pe prima linie n s , i m separate printr-un spat , iu, apoi pe
urm˘atoarele m linii nodurile muchiilor separate prin cˆate un spat , iu.

Date de ie¸sire
Fis , ierul de ies , ire conex3.out va cont , ine pe prima s , i a doua linie muchiile cerute ˆın enunt , .

Exemplu