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 ndgp.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 ndgp.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
| ndgp.in | ndgp.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 2 | 14 |
Explicatie
In primul exemplu graful este un arbore si deci are un singur graf partial conex (orice muchie am elimina, graful devene 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.
