Fişierul intrare/ieşire:count.in, count.outSursăpreONI 2006 Runda 3
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.7 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Count

Fiind dat un graf planar cu N noduri si M muchii aflati numarul maxim de noduri pe care il poate avea un subgraf complet al sau (un graf neorientat se numeste complet daca exista muchie intre oricare doua noduri ale sale). De asemenea se cere si numarul de subgrafuri complete cu numar maxim de noduri care se gasesc in graful planar dat.

Cerinta

Fiind dat un graf planar aflati cele doua numere cautate.

Date de Intrare

Linia 1 a fisierului de intrare contine doua numere naturale separate prin spatii N si M (numarul de noduri, respectiv numarul de muchii ale grafului planar).
Liniile 2 .. M + 1 contin cate doua numere A si B cu semnificatia: exista o muchie bidirectionala intre nodurile A si B (nodurile grafului sunt numerotate de la 1 la N).

Date de Iesire

Fisierul de iesire va contine pe prima linie doua numere X si Y reprezentand numarul maxim de noduri pe care il poate avea un subgraf complet si, respectiv, numarul de subgrafuri complete cu X noduri din graful planar dat.

Restrictii si precizari

  • 2 ≤ N ≤ 30 000
  • 1 ≤ M ≤ 60 000
  • Y ≤ 2^30
  • Pentru 70% din teste N ≤ 2000

Exemplu

count.incount.out
5 8
1 2
1 3
1 5
2 4
2 5
3 4
3 5
4 5
3 4

Explicatii

Se pot forma 4 subgrafuri complete cu 3 noduri. Acestea sunt:
(1 2 5), (2 4 5), (3 4 5), (1 3 5)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content