|
Titlul: CTC mai repede Scris de: nivan din August 25, 2006, 13:16:28 Exista vreo metoda mai rapida decat O( (N+M) * nr_de_componente )... de a calcula componentele tari conexe ?
Titlul: Raspuns: CTC mai repede Scris de: Tiberiu-Lucian Florea din August 25, 2006, 13:38:27 Da, si e descrisa in Cormen la capitolul de componente TARE conexe (nu tari conexe).
Titlul: Raspuns: CTC mai repede Scris de: nivan din August 25, 2006, 13:45:22 In cormen nu m-am uitat la asta.... ca invatasem mai demult in alta parte.
Titlul: Raspuns: CTC mai repede Scris de: Cosmin Negruseri din August 26, 2006, 00:59:52 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)
Titlul: Raspuns: CTC mai repede Scris de: nivan din August 26, 2006, 12:01:53 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). Titlul: Raspuns: CTC mai repede Scris de: Cosmin Negruseri din August 26, 2006, 12:20:33 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) 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. Titlul: Raspuns: CTC mai repede Scris de: nivan din August 26, 2006, 12:39:52 ms... am inteles :D
|