Page 98 - MATINF Nr. 4

˘
98 PROBLEME DE INFORMATICA PENTRU CONCURSURI

Exemplu

saranjam.in saranjam.out Explicatie
2 5 aranjam(3,1) + aranjam(4,2) = 3 + 12 = 15
3 1
4 2

Timp maxim de execut , ie: 1 secund˘a/test.
Memorie total˘a disponibil˘a 4 MB.

Alexandru Ion Popescu, Bucures , ti

I 58 (turneu). Se d˘a un graf orientat prin n num˘arul de noduri, m num˘arul de arce ¸si nodurile
arcelor (1 < n < 150).

Cerint , ˘a

Pentru un graf orientat, determinat , i num˘arul de componente tari conexe care sunt grafuri
turneu.

Date de intrare

Pe prima linie a fisierului turneu.in se afl˘a n ¸si m cu un spat¸iu ˆıntre ele. Pe urm˘atoarele m
linii se afl˘a perechi de noduri reprezentˆand arce.

Date de ie¸sire

Pe prima linie a fi¸sierului turneu.out se va scrie num˘arul din cerint¸˘a.

Exemplu

turneu.in turneu.out Explicatie
8 11 2 Graful cont , ine 3 componente tari conexe.
3 1 Componentele tari conexe care sunt
1 8 grafuri turneu:
8 3 1 3 8
3 4 2 5 6 7
4 5
5 6
6 7
7 2
2 5
5 7
6 2

Timp maxim de execut , ie: 1 secund˘a/test.
Memorie total˘a disponibil˘a 4 MB.

Doru Constantin, Pites , ti