Graf2

graf2

== include(page="template/taskheader" task_id="graf2") ==

Se da un graf orientat $A=(V, E)$ si se zice ca exista drum de la $X$ la $Y$ ({$X$}, $Y$ apartin lui $V$) daca pornind de la $X$ si mergand pe arcele grafului se poate ajunge in $Y$. Sa se gaseasca numarul minim de arce ale unui graf $B=(V,E{~2~})$ cu proprietatea ca exista un drum de la $X$ la $Y$ in graful $B$ daca si numai daca exista un drum de la $X$ la $Y$ in graful $A$.
 

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $graf2.in$ se afla pe prima linie doua numere intregi $N$ si $M$ reprezentand numarul de noduri si respectiv numarul de arce ale grafului $A$. Pe urmatoarele $M$ linii se vor afla cate doi intregi $X$ si $Y$ reprezentand faptul ca in graful $A$ exista arc de la $X$ inspre $Y$.

Fişierul de intrare $graf2.in$ ...

h2. Date de ieşire

În fişierul de ieşire $graf2.out$ se va afla un singur numar reprezentand numarul minim de arce ale grafului $B$.

În fişierul de ieşire $graf2.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 600$
* $1 ≤ M ≤ 10.000$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. graf2.in |_. graf2.out |

| 3 3
  1 2
  2 3
  1 3
| 2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Se poate crea graful $B$ cu arcele $1->2$ si $2->3$, respectandu-se proprietatea grafului.

...

== include(page="template/taskfooter" task_id="graf2") ==

== include(page="template/taskfooter" task_id="graf2") ==
 

7392