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.
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’$}.
Dupa sortarea listelor de adiacenta, se efectueaza o parcurgere DF din radacina lui {$G*$}.
_Propozitie 1_
_Propozitie 1_:
==Include(page="template/preoni-2007/footer")==
