Diferente pentru problema/graf2 intre reviziile #16 si #28

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="graf2") ==
Anca , vazand ca ONI 2012 se apropie cu pasi repezi , s-a hotarat s-o ajute pe sora ei mai mica ( Gabi ) sa se pregateasca. Dar , dupa ce i-a aratat cativa algoritmi pe grafuri , a vazut ca aceasta ii cunostea si ca incepuse sa se plictiseasca. Asa ca s-a gandit sa ii arate o problema pe care o invatase de la ultimul ei profesor. Problema suna asa:
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$.
"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 le muchiile grafului se poate ajunge in $Y$.
Sa se gaseasca numarul minim de muchii ale unui graf $B=(V,E{~2~})$ cu proprietatea ca daca exista drum de la $X$ la $Y$ in graful $A$ , atunci exista drum de la $X$ la $Y$ si in graful $B$."
 
Saraca Anca! Intr-un moment a uitat rezolvarea problemei. Acum ea va roaga sa o ajutati sa-si reaminteasca rezolvarea si in schimb va promite 100 de puncte si tot norocul in fazele urmatoare ale concursului.
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 muchii ale grafului $A$. Pe urmatoarele $M$ linii se vor afla cate doi intregi $X$ si $Y$ reprezentand faptul ca in graful $A$ exista muchie de la $X$ inspre $Y$.
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$.
h2. Date de ieşire
În fişierul de ieşire $graf2.out$ se va afla un singur numar reprezentand numarul minim de muchii ale grafului $B$.
În fişierul de ieşire $graf2.out$ se va afla un singur numar reprezentand numarul minim de arce ale grafului $B$.
h2. Restricţii
* $1 ≤ N ≤ 100000$
* $1 ≤ M ≤ 200000$
* $1 ≤ N ≤ 600$
* $1 ≤ M ≤ 10.000$
h2. Exemplu
h3. Explicaţie
Se poate crea graful $B$ cu muchiile 1->2 si 2->3 , respectandu-se proprietatea grafului
Se poate crea graful $B$ cu arcele $1->2$ si $2->3$, respectandu-se proprietatea grafului.
== include(page="template/taskfooter" task_id="graf2") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
7392