Page 102 - MATINF Nr. 6

˘
102 PROBLEME DE INFORMATICA PENTRU CONCURSURI

I 88 (arce). Se d˘a un graf orientat cu n noduri s , i m arce. Pentru acest graf se dores , te
determinarea num˘arului cel mai mare de arce care se g˘asesc ˆıntr-o component tare conex˘a.

Cerint , ˘a
Cunoscˆand n, m s , i cele m arce se cere s˘a se determine num˘arul cel mai mare de arce care se
g˘asesc ˆıntr-o component tare conex˘a.

Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 100

Date de intrare

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

Date de ies , ire

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

Exemplu

arce.in arce.out Explicat , ie
7 8 4 Graful cont , ine 3 componente conexe.
1 2 Componenta conex˘a cu cele mai multe arce
5 6 are nodurile 1, 2, 3 s , i 4 arce.
6 5
2 3
3 2
6 7
5 1
3 1

Doru Anastasiu Popescu, Pites , ti

I 89 (lant). Se d˘a un graf neorientat conex cu n noduri s , i m muchii. Pentru acest graf se
dores , te determinarea unui lant , elementar care s˘a cont , in˘a toate nodurile grafului, dac˘a exist˘a.

Cerint , ˘a

Cunoscˆand n noduri s , i cele m muchii se cere s˘a se determine un lant , elementar care s˘a
cont , in˘a toate nodurile grafului.
Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 1000

Date de intrare

Fis , ierul lant.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 ies , ire

Fis , ierul de ies , ire lant.out va cont , ine pe prima linie nodurile lant , ului din cerint , ˘a separate
prin cˆate un spat , iu. Dac˘a nu exist˘a un astfel de lant , se va scrie cifra 0.