Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-08 23:41:49.
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

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.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?