| Fişierul intrare/ieşire: | gminmax.in, gminmax.out | Sursă | Algoritmiada 2009, Runda 3 |
| Autor | Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | gminmax.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.
