Diferente pentru problema/ndap intre reviziile #19 si #39

Diferente intre titluri:

Numarul de arbori partiali
Ndap

Diferente intre continut:

== include(page="template/taskheader" task_id="ndap") ==
TODO(alexandru.mosoi): graf nu arbore (varza...)
Fie $G = (V, E)$ un graf neorientat cu $V$ multimea varfurilor, iar $E$ multimea muchiilor. Definim un **graf partial** a lui $G$ graful $P = (V, E')$ cu $E'$ inclus in $E$.
Fie $G = (V, E)$ un graf neorientat cu $V$ multimea varfurilor, iar $E$ multimea muchiilor. Definim un **graf partial** a lui $G$ graful $P = (V, E')$ astfel incat $E'$ este inclus in $E$.
 
Dandu-se G, **un graf neorient conex**, se cere sa se determine cate **grafuri partiale conexe** are graful G.
Dandu-se $G$, **un graf neorientat conex**, se cere sa se determine cate **grafuri partiale conexe** are graful $G$.
h2. Date de intrare
Pe prima linie din fisierul de intrare $ndap.in$ contine doua numere $N$ si $M$ reprezentand numarul de noduri, respectiv numarul de muchii din graful G. In continuare in fisier se vor afla $M$ linii ce descriu grafului. Pe linia $i+1$, cu $1 ≤ i ≤ M$, se vor afla doua numere $a{~i~} b{~i~}$ cu semnificatia ca exista o muchie de la $a{~i~}$ la $b{~i~}$ in $G$.
Pe prima linie din fisierul de intrare $ndap.in$ contine doua numere $N$ si $M$ reprezentand numarul de noduri, respectiv numarul de muchii din graful $G$. In continuare in fisier se vor afla $M$ linii ce descriu grafului. Pe linia $i+1$, cu $1 ≤ i ≤ M$, se vor afla doua numere $a{~i~} b{~i~}$ cu semnificatia ca exista o muchie de la $a{~i~}$ la $b{~i~}$ in $G$. Nodurile vor fi numerotate de la $0 la N$-1.
h2. Date de iesire
  1 2
  2 3
  3 0
| 4
| 5
|
| 4 5
  0 1
  1 2
  2 3
  3 0
  1 2
| 8
1 3
| 14
|
h3. Explicatie
In primul exemplu graful este deja un arbore si deci are un singur arbore partial.
In exemplul al doilea graful este un ciclu format din 4 muchii. Exista 4 arbori partiali doarece oricare muchie s-ar elimina din graf s-ar obtine un arbore partial.
In primul exemplu graful este un arbore si deci are un singur graf partial conex (orice muchie am elimina, graful devine neconex).
In exemplul al doilea graful este un ciclu format din 4 muchii. Exista 5 grafuri partiale doarece se poate elimina cel mult o muchie pentru ca graful sa ramana conex.
== include(page="template/taskfooter" task_id="ndap") ==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2051