Page 122 - MATINF Nr. 3

˘
122 PROBLEME DE INFORMATICA PENTRU CONCURSURI

Exemplu

scombinare.in scombinare.out Explicatie
2 9 comb(3,1) + comb(4,2) = 3 + 6 = 9.
3 1
4 2

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

Alexandru Ion Popescu, Bucures , ti

I 43 (tconex). Se d˘a un graf orientat prin n - num˘arul de noduri, m - num˘arul de arce ¸si
perechile de noduri reprezentˆand arcele (1 < n < 15).
Cerint , ˘a

Pentru un graf dat, determinat , i num˘arul de arce care nu se reg˘asesc ˆın nicio component˘a
tare-conex˘a.
Date de intrare

Pe prima linie a fis , ierului tconex.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 arcele.
Date de ie¸sire

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

tconex.in tconex.out Explicatie
4 5 1 Graful cont , ine dou˘a componente tare-conexe.
1 4 Arcul (4,3) nu are ambele noduri ˆın aceeas , i
4 3 component˘a tare-conex˘a.
4 1
3 2
2 3

Timp maxim de execut , ie: 1 sec./test. Memorie total˘a disponibil˘a 4 MB.
Doru Constantin, Pites , ti

I 44 (abs). Se d˘a un graf neorientat ponderat conex prin n - num˘arul de noduri, m - num˘arul de
muchii ¸si prin triplete formate din extremit˘at , ile muchiilorˆımpreun˘a cu ponderile corespunz˘atoare.
Cerint , ˘a

Pentru un graf neorientat ponderat conex s , i un num˘ar natural S, determinat , i un arbore
part , ial (muchiile sale) cu costul S.
Date de intrare

Pe prima linie a fis , ierului aps.in se afl˘a n, m s , i S, separate prin cˆate un spat¸iu. Pe
urm˘atoarele m linii se afl˘a triplete de numere reprezentˆand extremit˘at , ile s , i costul pentru fiecare
muchie.

Date de ie¸sire

Pe n − 1 linii ale fi¸sierului aps.out se va scrie cˆate o muchie, pentru un arbore part , ial de
cost S.