h3. (problema grea, clasele 11-12)

Putem asocia problemei un graf orientat care are proprietatea:
 
(*): Oricum am alege 3 noduri {$A$}, {$B$}, {$C$} din graf astfel incat sa existe drum de la {$A$} la {$C$} si de la {$B$} la {$C$}, atunci exista drum de la {$A$} la {$B$} sau de la {$B$} la {$A$} ( posibil ambele ).
 
Un query {$(x y)$} cere determinarea numarului minim de arce care trebuiesc reorientate astfel incat sa avem drum de la $x$ la {$y$}. Problema se poate rezolva optim in complexitate {$O(N + M + T)$}, dar in concurs o solutie {$O( (N + T) log N + M log M )$} era suficienta pentru obtinerea punctajului maxim.
 
Graful initial se transforma intr-un graf aciclic, graful componentelor tare conexe, pe care il vom nota {$G’$}. In continuare, cand ne referim la nodul $x$ in {$G’$} ne referim la nodul componentei tari conexe care il contine pe {$x$}. Numim radacina pentru {$G’$} acel nod care are gradul intern $0$ ( nodul in care nu intra nici o muchie ). Exista un singur astfel de nod, deoarece, daca ar exista cel putin doua, conditia (*), impreuna cu proprietatea de conexitate a grafului suport, nu ar mai fi respectata.
Cum {$G’$} este aciclic, putem sorta nodurile lui astfel incat daca exista muchie de la $x$ la $y$ in {$G’$}, $x$ va aparea inaintea lui $y$ in sortare ( sortare topologica ). Pentru fiecare nod din {$G’$} sortam lista lui de adiacenta conform ordinii din sortarea topologica. Sortarea se poate face liniar, cu radixsort, sau cu algoritmul quicksort.
 
Dupa sortarea listelor de adiacenta, se efectueaza o parcurgere DF din radacina lui {$G’$}.
 
_Propozitie 1_
 

==Include(page="template/preoni-2007/footer")==