Fişierul intrare/ieşire:drumuri2.in, drumuri2.outSursăLot 2005
AutorEmilian MironAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Drumuri2

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, ..., xk) astfel incat pentru orice i din {1, 2, ..., k-1}, exista arcul (xi, xi+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 drumuri2.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.

Date de iesire

Fisierul de iesire drumuri2.out va contine o singura linie reprezentand numarul minim de drumuri cu care se poate acoperi graful din fisierul de intrare.

Restrictii

  • 1 ≤ N ≤ 100
  • 1 ≤ M ≤ 5000

Exemplu

drumuri2.indrumuri2.out
7 7
1 2
7 2
2 3
2 4
3 5
4 5
4 6
2

Explicatii

D1: 1->2->3->5
D2: 7->2->4->6

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content