Cykl w grafie skierowanym

Mam problem z takim zadankiem, mamy pusty graf i dodajemy do niego skierowane krawędzie, trzeba stwierdzić kiedy w grafie powstanie cykl. Sądzac po limitach to rozwiązanie musi być liniowe, max nlogn, ma ktoś jakiś pomysł (nie licząc bruta dfs'em)?
Jeżeli nie ten dział to sorry, ale nie widziałem nic o algorytmach

Idąc wraz z dodawaniem, dla każdego samotnego grafu ustawiasz jakiś numer id. Jeśli połączysz graf z grafem (tzn. wierzchołek z numerem id z wierzchołkiem z innym numerem id), to tworzysz nowy numer id oznaczający połączony graf, a dwa obecne id ustawiasz jako wskazujące na nowe.
Stwierdzenie czy istnieje cykl - podczas łączenia dwóch grafów sprawdzasz, czy id obu wierzchołków w pewnym momencie się spotka (idąc wraz z nowymi odniesieniami).

Tworzenie grafu - n lg n
Sprawdzanie jednego - lg ilosc_odniesien

Użyj do tego celu zbiorów rozłącznych (poszukaj w necie opisu ew).

P.S oig? bo juz to tłumaczyłem kiedyś

Nie wiem, czy da się w O(n), ale O(n lg n) jest bardzo proste

Kilka podpowiedzi:
-jeżeli dodajesz nową krawędź do grafu i był już cykl, to cykl dalej będzie
-skup się nie na zwiększeniu szybkości pojedynczego kroku(zwykły DFS O(n) jest ok), a na zmniejszeniu liczby kroków
-wyszukiwanie binarne

można prosić trochę jaśniej? :d
gdzie zastosować wyszukiwanie binarne?

Wydaje mi się, że algorytm zbiorów rozłącznym nie będzie dobrze działał w przypadku grafów SKIEROWANYCH :P chyba, że jakoś przerobić, bo np. w algorytmie kruskala się tego używa, ale tam są zazwyczaj grafy nieskierowane :p

Czy to jest zadanie ogólnodostępne ? Np. z jakiejś sprawdzarki, typu opss, spoj, czy podobnej ? Jeśli tak to plz podaj linka :)

Liczba cykli w grafie po dodawaniu kolejnych krawędzi może np. wyglądać tak:
0000000111111223... (tu pierwszy cykl powstał przy 8. krawędzi)

Wyszukiwanie binarne po wyniku

Mamy np. 10^6 krawędzi w całym grafie.
Sprawdzamy, czy w 10^6/2 iteracji był co najmniej jeden cykl.
Jak był to szukamy w przedziale <1, 10^{6/2>, a jak nie to <10}6/2 + 1, 10^6>.

Czyli wystarczy nam O(lgN) sprawdzeń o koszcie O(N).

Można nawet nie tworzyć za każdym razem nowego grafu, wystarczy przy każdej krawędzi pamiętać jedną dodatkową wartość...mam nadzieję, że się domyślisz jaką.

Całość jest bardzo prosta. Kod zajmie pewnie z 50 linii.

wielkie dzięki __krzysiek85, już wiem o co chodzi

Spykaj napisał(a)

Czy to jest zadanie ogólnodostępne ? Np. z jakiejś sprawdzarki, typu opss, spoj, czy podobnej ? Jeśli tak to plz podaj linka :)
http://ki.staszic.waw.pl/task.php?name=zabytki

wow, __krzysiek85, nieźle :) podoba mi się to rozwiązanie :D sam bym na lepsze nie wpadł