-
Robisz bfs z losowego, nieodwiedzonego odcinka, zapisując głębokość przy każdym węźle (jako wskaźnik do zmiennej!) + numer przeszukiwania
Gdy spotkasz cykl do odwiedzonego elementu (czyli dojdziesz do elementu początkowego), cofając się, ustaw wskaźniki głębokości wszystkich poprzednich węzłów w cyklu (wyższych węzłów w bfs) na najmniejszą głębokość w cyklu (ten sam wskaźnik do jednej zmiennej).
W jakiś sposób zaznacz, że to jest wskaźnik do głębokości cyklowej (wskaźnik do struktury z takim polem?), żeby potem wiedzieć, że nie trzeba chodzić w prosty sposób.
Gdy w innym cyklu spotkasz cykl do innego cyklu, nie będziesz musiał się znowu cofać po wszystkich elementach (co w najgorszym przypadku dałoby ci złożoność kwadratową całości) ale zmieniasz tylko w jednym miejscu wartość wskaźnika i nie musisz iść dalej.
Po skończeniu całego wyszukiwania masz las, w którym z każdego węzła o głębokości 1 można dojść do wszystkich elementów.
Złożoność jest ciągle liniowa, ale ze współczynnikiem stałym 2
-
Po zakończeniu sprawdzasz, czy przeszedłeś po wszystkich istniejących
jak tak, to win (patrz trochę poniżej co dalej)
jak nie, to powtarzasz punkt 1 i jak przy bfsie spotkasz odwiedzony wierzchołek przez poprzedni bfs (czyli inny numer szukania) sprawdź jego głębokość, jeśli 1 to ustawiasz napotkany las jako syna obecnego lasu w meta-drzewie (patrz niżej). Jeśli inna głębokość, to po prostu zignoruj ten węzeł - nie musisz tam wchodzić, bo i tak wiesz, że nie da ci to dostępu do wszystkich wierzchołków - albo dojdziesz skądś indziej do wierzchołka z numerem 1 (w tym samym wyszukiwaniu), albo to nie jest ten wierzchołek.
Meta-drzewo - będziesz tam zapisywał numery lasów, z którego można dojść do którego.
Np. w wyszukiwaniu 2 (licząc od 1) doszedłeś do wierzchołka 1 wyszukiwania 1.
Meta-drzewo będzie wyglądało tak
2->1
Czyli, że z lasu 2 możesz dojść do lasu 1.
Uwaga: meta-drzewo może być rozłączne. Np.
2->1 4->5
|
3
Rób to wszystko aż skończą ci się nieodwiedzone elementy.
Jak się skończą, będziesz miał meta-drzewo ze wszystkimi numerami lasów, z których każdy reprezentuje część całego grafu.
Element, z którego można dojść wszędzie, istnieje, jeśli meta-drzewo nie jest rozłączne, tzn. istnieje las z którego można dojść do wszystkich innych lasów.
(to już można sprawdzić banalnie).
Elementami tymi są wszystkie wierzchołki z lasu będącego czubkiem meta-drzewa (dokładnie jeden - meta-drzewo musi być acykliczne, to wynika ze sposobu jego budowy) o głębokości 1.
Koniec końców masz coś o złożoności nie większej niż 2(m+n).