CTC mai repede

[nivan]

 Exista vreo metoda mai rapida decat O( (N+M) * nr_de_componente )... de a calcula componentele tari conexe ?

[•greco]

Da, si e descrisa in Cormen la capitolul de componente TARE conexe (nu tari conexe).

[nivan]

In cormen nu m-am uitat la asta.... ca invatasem mai demult in alta parte.

[•Cosmin]

Nu stiu nici o metoda de complexitate O((N + M) * nr_componente). Poti sa explici putin? (te intreb asta pentru ca am impresia ca zici de aceiasi metoda ca cea din cormen)

[nivan]

mda... iau un nod x... calculez predecesorii si sucesorii lui X cu doua DFS-uri.

PREDECESOR = se poate ajunge el in x
SUCESOR = se poate ajunge din x in el

apoi orice nod y care e si predecesor si sucesor a lui x il includ in aceiasi componenta cu x.

OBS: la prima vedere pare eronat, dar nu e...daca din y pot ajunge in x si din x in orice nod din componenta... se dovedeste adevarat.

Apoi trec la alt nod x, care nu a fost inclus inca in nici o componenta.

Daca calculez complexitatea imi iese 2*O(N+M) de la cele 2 DFS-uri + O(numarul de componente). adica O(2*(N+M)*numaru_de_componente)... aproximativ O( (N+M) * numarul_de_componente).

[•Cosmin]

Ok, am inteles. Eu la algoritmul asta ma gandeam ca are complexitatea O(N^3) daca ii dai ca intrare un graf acciclic complet, dar intradevar aici sunt n componente tari conexe diferite.

Ideea e urmatoarea:
Faci niste dfs-uri si scrii nodurile intr-o lista ca la o sortare topologica a unui graf acciclic

Cod:

dfs(v) 
  dfs(w) unde exista arcul (u, w) si w nu e vizitat inca
  adauga v la lista nodurilor

Acum daca inversam sensurile arcelor din graf, componentele tari conexe raman aceleasi. Dar din componenta tare conexa a ultimului nod adaugat in lista nu va exista nici un arc care iese. Poti demonstra asta cu inductie matematica sau sa te joci cu cateva exemple. Pentru a determina componenta tare conexa a acestui nod, este suficient acum sa facem un dfs din el. Cautarea va atinge doar nodurile si arcele componentei conexe curente. Astfel putem sterge logic aceasta componenta tare conexa si sa facem dfs din nou de la ultimul nod ramas in lista.

[nivan]

ms... am inteles