Fişierul intrare/ieşire:gminmax.in, gminmax.outSursăAlgoritmiada 2009, Runda 3
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.4 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gminmax

Fie un graf neorientat cu N noduri si M muchii. Se cere un subgraf cu numar maxim de noduri, astfel incat gradul minim al unui nod din subgraf sa fie cat mai mare (gradul nodului se calculeaza in cadrul subgrafului si nu a intregului graf initial).

Date de intrare

Fişierul de intrare gminmax.in contine pe prima linie numerele N si M separate printr-un spatiu. Urmatoarele M linii contin fiecare cate doua numere x si y reprezentand faptul ca intre x si y se afla o muchie.

Date de ieşire

Fisierul de iesire gminmax.out va contine doua numere separate printr-un spatiu reprezentand gradul minim maxim ce se poate optine intr-un subgraf si dimensiunea maxima a unui subgraf care respecta aceasta proprietate.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 500 000
  • Nu vor exista muchii duble sau muchii de la un nod la acelasi nod

Exemplu

gminmax.ingminmax.out
7 10
1 2
1 3
1 4
2 3
2 4
3 4
4 5
5 6
6 4
3 7
3 4

Explicaţie

Daca alegem subgraful format din nodurile 1, 2, 3 si 4 gradul minim al unui nod este 3. Nici un alt subgraf nu are gradul minim al unui nod mai mare ca 3 si acest subgraf este cel mai mare care respecta acest grad.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content