Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ndap.in, ndap.out | Sursă | Summer Challenge 2007, runda 3 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Alexandru Mosoi •alexandru.mosoi |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | ndap.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.
