Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-08 21:37:09.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:ndap.in, ndap.outSursăSummer Challenge 2007, runda 3
AutorCosmin Silvestru NegruseriAdăugată dealexandru.mosoiAlexandru Mosoi alexandru.mosoi
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ndap

TODO: graf nu arbore (varza...)

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.

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

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 ai bi cu semnificatia ca exista o muchie de la ai la bi in G.

Date de iesire

In fisierul de iesire ndap.out se va scrie pe prima linie numarul cerut in enunt modulo 30103.

Restrictii

  • 1 ≤ N ≤ 15
  • 0 ≤ ai, bi ≤ N-1
  • orice muchie va aparea cel mult o data in fisierul de intrare

Exemplu

ndap.inndap.out
4 3
0 1
2 1
1 3
1
4 4
0 1
1 2
2 3
3 0
4
4 5
0 1
1 2
2 3
3 0
1 2
8

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?