Ndap

Numarul de arbori partiali

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

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 unde V este multimea varfurilor, iar E este inclus in $V x V$ (produs cartezian dintre $V$ si $V$) este multimea de muchii. Definim arborele partial a lui $G$ un graf $A = (V, E')$ astfel incat $E'$ este inclus in $E$, iar intre oricare doua noduri din $V$ exista exact un drum in graful $A$.

Dandu-se $G$, **un graf neorientat conex**, se cere sa se determine cate **grafuri partiale conexe** are graful $G$.

Danduse un graf neorient, G, se cere sa se determine numarul de arbori partiali a grafului.

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$. Nodurile vor fi numerotate de la $0 la N$-1.

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 muchiile 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$.

h2. Date de iesire

h2. Restrictii

* $1 ≤ N ≤ 15$
* $0 ≤ a{~i~}, b{~i~} ≤ N-1$
* orice muchie va aparea cel mult o data in fisierul de intrare

* $ 1 ≤ N ≤ 15 $
* $ 0 ≤ a~i~, b~i~ ≤ N-1 $
* o muchie va aparea cel mult o data i fisierul de intrare

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

| 4 3
  0 1
  2 1
  1 3
| 1
|
| 4 4
  0 1
  1 2
  2 3
  3 0
| 5
|
| 4 5
  0 1
  1 2
  2 3
  3 0
1 3
| 14
|
 

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

h3. Explicatie

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") ==

2051