Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | drumuri2.in, drumuri2.out | Sursă | Lot 2005 |
| Autor | Emilian Miron | Adăugată de | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Drumuri2
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
drumuri
Se da un graf orientat fara circuite cu n noduri (numerotate de la 1 la n) si m arce.
Un drum in graf este o succesiune de unul sau mai multe varfuri D=(x1, x2, ..., x[k]) astfel incat pentru orice i I{1, 2, ..., k-1}, exista arcul (x[i], x[i+1]).
Numim acoperire a grafului o multime de drumuri din graf, cu proprietatea ca fiecare varf al grafului apartine cel putin unui drum din multime.
Nu este necesar ca drumurile dintr-o acoperire sa fie disjuncte (nici relativ la varfuri, nici relativ la arce).
Cerinta
Determinati numarul minim de drumuri cu care se poate acoperi un graf dat.
Date de Intrare
In fisierul de intrare drumuri.in se afla pe prima linie numerele naturale n si m, separate printr-un spatiu.
Pe fiecare dintre urmatoarele m linii se gaseste cate o pereche de numere naturale i, j (1 L i, j L n) separate printr-un spatiu, cu semnificatia ca exista arc de la varful i la varful j.
Date de Iesire
Fisierul de iesire drumuri.out va contine o singura linie reprezentand numarul minim de drumuri cu care se poate acoperi graful din fisierul de intrare.
Restrictii
o 1 <= n <= 100
o 1 <= m <= 5000
Exemplu
drumuri.in drumuri.out Explicatie
7 7 2 D1 : 1->2->3->5
1 2 D2 : 7->2->4->6
7 2
2 3
2 4
3 5
4 5
4 6
