Page 14 - MATINF Nr. 3

14 D.A. Popescu, C. B˘alc˘au, D. Constantin

ˆ
In acest caz, ˆın fis , ierul de ies , ire grafuri.out se vor scrie numerele de ordine (ˆın ordine
cresc˘atoare) ale grafurilor neorientate care sunt 2-neconexe echilibrate.

Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.
ˆ
In acest caz, ˆın fis , ierul de ies , ire grafuri.out se vor scrie numerele de ordine (ˆın ordine
cresc˘atoare) ale grafurilor neorientate care sunt aproape 2-neconex echilibrate.

Restrict , ii s , i preciz˘ari

• 1 ≤ T ≤ 20; 1 ≤ n i ≤ 200, 1 ≤ i ≤ T
• Orice graf 2-neconex echilibrat este s , i aproape 2-neconex echilibrat
• Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 40% din punctaj, iar pentru cerint , a 2 se
acord˘a 60% din punctaj

Exemple

grafuri.in grafuri.out Explicat , ie
1 1 p = 1
3 Primul graf neorientat este 2–neconex echilibrat, celelalte
4 2 dou˘a grafuri nu sunt 2–neconex echilibrate.
1 2
3 4
7 4
1 3
2 6
1 7
7 5
6 1
1 4
grafuri.in grafuri.out Explicat , ie
2 1 3 p = 2
3 Primul s , i al treilea graf neorientat sunt aproape 2–neconex
4 2 echilibrate. Primul graf este 2–neconex echilibrat s , i implicit
1 2 aproape 2–neconex echilibrat. Al doilea graf are dou˘a
3 4 componente conexe, una cu 4 noduri s , i alta cu 2 noduri, deci
7 4 nu este graf aproape 2–neconex echilibrat. La al treilea graf,
1 3 dac˘a ad˘aug˘am, de exemplu muchiile [1,2], [3,5], [5,6] se obt , ine
2 6 un graf cu dou˘a componente conexe, fiecare cu cˆate 3 noduri,
1 7 deci graful este aproape 2–neconex echilibrat.
7 5
6 1
1 4

Timp maxim de execut , ie: 0.1 secunde/test.
Memorie total˘a disponibil˘a 4 MB.
Dimensiunea maxim˘a a sursei: 5 KB.

Solut , ie

Dac˘a num˘arul de noduri este impar, graful nu verific˘a nicio condit , ie dintre cele dou˘a definite
ˆın enunt , . Pentru prima cerint , ˘a folosim parcurgerea ˆın l˘at , ime sau ˆın adˆancime, de cel mult de