W [CLR] jest takie zadanie (22.4-3). Podaj algorytm sprawdzania, czy dany graf nieskierowany G=(V,E) ma cykl. Twoj algorytm powinien dzialac w czasie O(V) niezaleznym od |E|.
Jak to zrobic? Jest to pod koniec dzialu o sortowaniu topologicznym - nie widze tu zastosowania dla tego algorytmu bo dziala on w O(E+V) :( Szczerze mowiac to w ogole nie wiem jak to zrobic w takim czasie.
i przy okazji... takie male pytanko: czy do "Podaj kontrprzyklad do hipotezy mowiacej, ze jesli istnieje sciezka od u do v w grafie skierwanym G, to w dowolnym przeszukiwaniu dostaniemy d[v]<=f[u]" dobrym kontrprzykladem jest przeszukiwanie wszerz? ;)) Pytam, bo to pytanie jest do przeszukiwania w glab, z druiej strony przy innych pytaniach jest wyraznie zaznaczone ze chodzi o w glab a tu jest napisane dowolne [green]
// Edit: Moze komus sie to przyda wiec odpowiem :)
Problem jest banalny - wystarczy przeszukac graf (BFS lub DFS) i w momencie napotkania odwiedzonego wierzcholka wypisac, ze jest cykl. Bedzie to O(V) dlatego, ze kazdy wierzcholek zostanie odwiedzony conajwyzej raz, a w momencie gdyby krawedzie mialy miec jakis wplyw to zostanie wypisane, ze jest cykl juz przy pierwszej powtarzajacej sie krawedzi
[soczek]