057 Diametrul unui arbore

[•Teodor94]

Aici puteti discuta despre problema Diametrului unui arbore.

[•CosminRusu]

In primul rand, felicitari tuturor celor implicati in extinderea arhivei educationale , iar in al doilea rand cred ca ati uitat sa puneti acces liber si la teste.
Numai bine!

[•proflaurian]

O solutie tot in O(N) ar fi sa se inceapa o parcurgere BF plecand din frunze cu scaderea gradului odata cu eliminarea unei muchii si introducerea in coada a unui nod numai cand ajunge frunza (ideea e oarecum similara cu cea de la sortarea topologica). In felul asta solutia este suma distantelor pana la ultimele doua noduri parcurse ( distanta este calculata bineinteles din nod pana la cea mai indepartata frunza ). O implementare pe aceasta idee :
http://www.infoarena.ro/job_detail/1106081?action=view-source

[•sorin_olimpiqu]

Am 2 obiectii

1. Sursa mea de Java care implementeaza tot 2 BFS nu intra in timp.
2. In enunt nu scrie clar, ca radacina este mereu 1. In implementare se vede in schimb ca autorul presupune asta pentru teste. Se vede ca cineva care nu cunoaste o oarecare conventie nu are cum sa stie ca radacina este mereu 1. In mod normal as mai fi pierdut vreme ca sa o determin.

[•PlayLikeNeverB4]

1. Am reusit maxim 90. Nu cred ca intra in Java solutia asta. Ar merge marita putin limita.
2. E arbore fara radacina. Nu conteaza din ce nod pornesti cu primul bfs.

[•astronovice]

Salut,

Uitandu-ma peste solutia recomandata de 100pct, am observat urmatorul lucru:

Cod:

    #define MAX_N 1000001
    ...
    int contor[MAX_N],viz[MAX_N];
    ...
    memset(contor,0,MAX_N);
    memset(viz,0,MAX_N);

1. al 3-lea argument al lui memset primeste un numar de bytes nu de elemente. In acest caz sizeof(int) * MAX_N ar fi fost corect. Altfel se intializeaza doar o parte din vector.

2. MAX_N e de 10 ori mai mare decat dimensiunea maxima a inputului, ceea ce inseamna ca desi memset-ul primeste argumentul gresit, totusi initializeaza o bucata suficient de mare din array incat sa functioneze pentru problema asta, sizeof(int) fiind cel mai probabil 4.