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
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.