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 neorientat 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. Nodurile vor fi numerotate de la 0 la N-1.

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
5
4 5
0 1
1 2
2 3
3 0
1 3
14

Explicatie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content