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
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.
Dandu-se G, un graf neorient conex, se cere sa se determine cate grafuri partiale conexe are graful G.
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.
