h2. Indicaţii de rezolvare

O prima idee ar fi cea mai evidenta, sa se aleaga prin backtracking muchiile care sa apartina Arborelui, dupa care se verifica prin un 'dfs':problema/dfs conectivitatea arborelui. Aceasta rezolvare este cea mai naiva si are complexitate $O(2^N^*N)$ si ar lua aproximativ $20$ de puncte.

O prima idee ar fi cea mai evidenta, sa se aleaga prin backtracking muchiile care sa apartina Arborelui, dupa care se verifica prin un 'DFS':problema/dfs conectivitatea arborelui. Aceasta rezolvare este cea mai naiva si are complexitate $O(2^N^*N)$ si ar lua aproximativ $20$ de puncte.

Presupunand ca sunt deja alese $N - 2$ muchii care nu formeaza cicluri, in alte cuvinte formeaza $2$ arbori, si trebuie sa se mai aleaga inca o muchie, este evident ca trebuie sa se aleaga 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.
Deci daca se sorteaza muchiile si se parcurg in ordinea sortarii, ne este mereu util sa bagam muchia minima cat timp aceasta nu creaza un cicluri. Aceasta solutie are complexitate $O(N*M + Mlog{~2~}M)$, deoarece iterarea prin cele $M$ muchii are complexitate {$O(M)$}, iar parcurgerea dfs pentru verificarea ciclurilor este {$O(N)$}. O astfel de solutie se poate vedea 'aici':job_detail/229653?action=view-source si ar trebui sa ia $40-50$ de puncte, depinzand de implementare.
Parcurgerea dfs este redundanta, deoarece verificarea daca $2$ noduri, cele pe care le leaga muchia, sunt in aceeasi grupa se poate face in $O(log{~2~}N)$ cu 'multimi disjuncte':/problema/disjoint. Astfel complexitatea se reduce la $O(M*log{~2~}N + M*log{~2~}M)$ pentru ca se alege fiecare muchie si pentru fiecare muchie se verifica in $O(log{~2~}N)$ utilitatea ei.Pentru o optimizare mai departe se pot apela diferite metode de sortare care se bazeaza pe inexactitatea reprezintarii numerelor in calculator. De obicei nu trebuie optimizata sortarea. O reprezentare grafica se poate gasi "aici":http://en.wikipedia.org/wiki/Kruskal%27s_algorithm. Acest algoritm se numeste Kruskal si implementarea sa se poate vedea 'aici':job_detail/229317?action=view-source.

h2. Aplicatii

* 'Desen':problema/desen

* 'Radiatie':problema/radiatie

* "Aviamachinations":http://acm.sgu.ru/problem.php?contest=0&problem=323

* "Prim":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1748

== include(page="template/taskfooter" task_id="apm") ==