== include(page="template/taskheader" task_id="drumuri2") ==
==Include(page="template/taskheader" task_id="drumuri2")==
Poveste ...
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=(x{~1~}, x{~2~}, ..., x{~k~})$ astfel incat pentru orice i din {${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).
h2. Cerinta
...
Determinati numarul minim de drumuri cu care se poate acoperi un graf dat.
h2. Restrictii
h2. 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 ≤ i, j ≤ N)$ separate printr-un spatiu, cu semnificatia ca exista arc de la varful $i$ la varful {$j$}.
h2. Date de intrare
h2. 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.
h2. Date de iesire
h2. Restrictii
...
* $1 ≤ N ≤ 100$
* $1 ≤ M ≤ 5000$
h2. Exemplu
| drumuri2.in | drumuri2.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. drumuri.in |_. drumuri.out |_. Explicatie |
| 7 7
1 2
7 2
2 3
2 4
3 5
4 5
4 6
| 2
| D1 : 1->2->3->5
D2 : 7->2->4->6 |
== include(page="template/taskfooter" task_id="drumuri2") ==
==Include(page="template/taskfooter" task_id="drumuri2")==
