h2. Indicaţii de rezolvare

*Cosmin*:
Nu e kruskal amortizat O(1), ziceti ca lumea ca de aici invata lumea si e nasol sa invete gresit.
 
Si nu e mare optimizare prim fata de kruskal, daca aveti ceva timpi comparativi puteti zice asta.
 
Ar mai fi o chestie de sublinitat ca in grafe dense se merita mai bine sa faci prim in O(N^2). Era o problema la o finala ginfo in care se cerea sa determini costul arborelui partial de cost minim cand grafu ti dat de niste puncte in plan ca noduri si distantele dintre pucte ca costuri pentru muchii.
 
 
 

O prima idee ar fi generarea tuturor submultimilor de $N-1$ muchii, verificarea daca muchiile selectate formeaza un arbore si retinerea solutiei optime. Aceasta rezolvare este cea mai evidenta dar are complexitate exponentiala si obtine aproximativ $20$ de puncte.
Presupunand ca sunt deja alese $N-2$ muchii care nu formeaza cicluri, in alte cuvinte formeaza $2$ arbori, trebuie sa se mai aleaga inca o muchie, si anume muchia minima care garanteaza conectivitatea arborilor. De la aceasta idee deducem ca cel mai bine ar fi sa adaugam muchii de cost minim, cat timp aceste muchii nu creaza cicluri.
Daca se sorteaza muchiile crescator dupa costul asociat si se parcurg in ordinea sortarii, este mereu util sa adaugam la solutie muchia de cost minim cat timp aceasta nu creaza un ciclu, sau altfel spus, nodurile pe care le uneste nu sunt deja in aceeasi componenta conexa. Aceasta solutie are complexitate $O(N*M + Mlog{~2~}M)$, deoarece iterarea prin cele $M$ muchii are complexitate {$O(M)$}, iar 'parcurgerea dfs':problema/dfs pentru verificarea ciclurilor se realizeaza in timp {$O(N)$} la fiecare pas. O astfel de solutie obtine 40-50 de puncte, in functie de implementare, si se poate vedea 'aici':job_detail/229653?action=view-source.