Fişierul intrare/ieşire:	diametru.in, diametru.out	Sursă	Algoritmiada 2015, Runda 3
Autor	Adrian Budau	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Diametru

Stelica, student eminent la Liceul International al Structurilor de date se pregateste de Bacalaureat si, ca orice alt elev de varsta lui, atunci cand gaseste ceva interesant fara nicio legatura cu Bacalaureatul amana tot ce are de facut ca sa studieze ce a gasit.
Astazi el a descoperit algoritmul pentru determinarea diametrului unui graf (diametrul unui graf este definit ca maximul distantei minime intre 2 noduri). Este un algoritm foarte simplu si usor de implementat asa ca evident l-a facut sa se gandeasca la tot felul de aplicatii. Algoritmul este urmatorul (descris in pseudocod):

INTRARE: un graf neorientat conex G(V, E) cu nodurile etichetate de la 1 la |V| (cardinal de V)
 nod_curent <- 1
 raspuns <- 0
 pentru K pasi executa
   afla distanta de la nod_current la toate celelalte (de exemplu printr-un bfs http://infoarena.ro/problema/bfs )
   next <- nodul cel mai indepartat de nod_curent astfel incat niciunea din perechile (next, nod_curent) si (nod_curent, next) sa nu mai fi fost aleasa
           in caz de egalitate se alege next la distanta maxima de nod_curent
           in caz de egalitate si dupa criteriul de  mai sus se alege next de valoare minima
   raspuns <- max(raspuns, distanta dintre nod_curent si next)
   nod_curent <- next

Acest algoritm, are o proprietate foarte interesanta: cand graful G e arbore se poate alege K = 2 si sigur variabila raspuns va contine la final diametrul arborelui. Pentru grafuri lucrurile nu stau chiar asa. Chiar si-asa Stelica este foarte concentrat pe acest algoritm si nu mai invata nimic pentru bacalaureat asa ca parintii lui v-au rugat sa gasiti un graf G astfel incat sa fie nevoie de un K cat mai mare pentru ca algoritmul sa determine raspunsul. Va vor puncta in functie de cat de mare veti reusi sa faceti K-ul pentru a-i arata lui Stelica ca nu este un algoritm bun si sa nu-si mai piarda timpul cu el.

Astfel daca veti reusi sa faceti K-ul sa fie cel putin:

• 10 - veti primi 30 de puncte
• 450 - veti primi 50 de puncte
• 10.000 - veti primi 75 de puncte
• 60.000 - veti primi 100 de puncte

Date de intrare

Fişierul de intrare diametru.in va contine textul integral al operei Floare Albastra de Mihai Eminescu pentru cei aflati in aceeasi situatie cu Stelica.

Date de ieşire

În fişierul de ieşire diametru.out trebuie sa contina descrierea unui graf neorientat conex.
Pe primul rand se vor gasi N si M, numarul de varfuri, respectiv numarul de muchii din graful generat de dumneavoastra.
Pe urmatoarele M linii trebuie sa se gaseasca 2 numere x_i si y_i cu semnificatia ca exista o muchie intre nodul cu indicele x_i si cel cu indice y_i.

Restricţii

• 1 ≤ numarul de noduri din graful generat de dumneavoastra ≤ 500
• Graful generat trebuie neaparat sa fie conex, altfel veti primi "Fisier de iesire corupt"
• Nu aveti voie sa aveti muchii de la un nod la el insusi sau multiple muchii intre acelasi perechi de noduri

Exemplu

Explicaţie

Pentru acest output veti lua 0 puncte dar este un exemplu de graf unde nu se gaseste diametrul cu K = 2, trebuie K >= 3.
Algoritmul va functiona asa:

• Din nodul 1 se merge in nodul 2 care e la distanta 1 (toate sunt egal departate de 1 dar 2 are valoarea ea mai mica)
• Din nodul 2 se merge in nodul 3 care e la distanta 1 (toate sunt egal departate de 2 dar perechea (1, 2) a fost deja aleasa iar dintre 3 si 4, 3 are valoarea mai mica)
• Din nodul 3 se merge in nodul 4 care e la distanta 2 (s-a ales 4 fiindca e singurul la distanta 2 de nodul 3, restul fiind doar la distanta 1)

Cum se trimit solutii?