Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | Invalid task identifier .in, Invalid task identifier .out | Sursă | Invalid task identifier |
| Autor | Invalid task identifier | Adăugată de | Invalid task identifier |
| Timp execuţie pe test | Invalid task identifier sec | Limită de memorie | Invalid task identifier kbytes |
| Scorul tău | Invalid task identifier | Dificultate | Invalid task identifier |
Vezi solutiile trimise | Statistici
Invalid task identifier
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.
