Kiedy krawędź utworzy cykl?

Mam graf o N-wierzchołkach bez krawędzi. Następnie po kolei dodaję krawędzie skierowane do tego grafu. W jaki sposób mogę szybko stwierdzić czy dodanie danej krawędzi spowoduje utworzenie cyklu w grafie?

Struktura zbiorów rozłącznych ;) Przechowuj dla każdego wierzchołka informacje o "przedstawicielu jego grupy". Początkowo każdy wierzchołek jest sam dla siebie przedstawicielem. Jeśli dołączasz krawędzią wierzchołek X do Y to ustawiasz że przedstawicielem X jest przedstawiciel Y.

W ten sposób aby sprawdzić czy dodanie nowej krawędzi utworzy cykl wystarczy sprawdzić czy przedstawiciel dodawanego wierzchołka jest taki sam jak przedstawiciel tego drugiego.

Samo sprawdzanie przedstawiciela jest rekurencyjne i musisz "skakać" aż trafisz na króla który sam dla siebie jest przedstawicielem. Warto przez to stosować "kompresje ścieżki" tzn kiedy łączysz dwa grafy/zbiory to każdemu wierzchołki z dołączanego zbioru ustawiasz przedstawiciela na króla ;)

@Shalom, zauważ że ten graf jest skierowany. Twoje podejście działa tylko dla grafów nieskierowanych.

Generalnie ten problem jest trudny. Wiesz coś więcej na temat danych wejściowych ?
Z tego co pamiętam to jest ten sam problem:
http://pl.spoj.com/problems/XIWTPZF/

@xawery faktycznie, przeoczyłem to skierowanie ;)
Niemniej jeśli ktoś ma pod ręką V² pamięci to można to nadal zrobić dość szybko, tzn średnio w O(1) (chociaż dodanie nowej krawędzi będzie kosztowniejsze). Musimy dla każdego wierzchołka pamiętać skąd można do niego dojść. Niestety będzie to kosztowne pamięciowo.
Jeśli dodajemy krawędź A->B to w zbiorze źródeł dla B zapamiętujemy sobie że można przyjść do niego z A oraz z całego zbioru dla A. Jak widać pesymistycznie taki zbiór źródeł będzie rozmiaru rzędu V, niemniej sprawdzenie w hashsecie czy w zbiorze źródeł znajduje sie wierzchołek X będzie średnio w czasie O(1). Więc dodając krawędź X->Y w O(1) możemy sprawdzić czy w źródłach dla X znajduje się Y. Jeśli nie to nie będzie cyklu.

ten algorytm chyba nie działa.
Powiedzmy, że mamy: A->B->C->D->E
teraz:
F->A
To co się dzieje, to A pamięta, ze jego źródłem jest między innymi F.
Zaś E pamięta, że jego źródłem jest:
A,B,C,D. Problem w tym, że on nie pamięta, że jego źródlem jest także F. Jeśli teraz dodasz krawędź E->F to ta krawędź utworzy cykl. Jednak w źródłach E nie ma F, nie wykryjemy
cyklu.

1. Rozumiem ze chodzi o A->B->C->D->E->F ?
2. o_O Ale "F" nie jest źródłem dla "A". Wręcz przeciwnie. Źródłem dla "F" jest "A"!
   Napisz może sensowny przykład bo póki co to ja nie wiem czym jest to twoje F...
   Algorytm nie moze nie działać ;) Każdy wierzchołek zna WSZYSTKIE wierzchołki z których można do niego przyjść. W efekcie wie że próba dodania krawędzi do któregokolwiek z tych wierzchołków utworzy cykl. Tu nie ma co nie działać. Jedyny minus to koszt pamięciowy.

Idee rozumiem. Jednak zwróćmy uwagę na koszt czasowy, nie tylko pamięciowy. Taka aktualizacja zbiorów źródeł będzie CIe kosztować.

1. Rozumiem ze chodzi o A->B->C->D->E->F ?

uwzględnij to, że musisz online odpowiadać czy obecnie dodana krawędź jest cyklotworząca, w moim przykłądzie dsotaejesz po kolei:
A->B
B->C
C->D
D->E
F->A
E->F

Och oczywiście, mowiłem juz wcześniej że aktualizacja zbiorów będzie kosztowna. Niemniej autor pytał tylko o szybkie sprawdzanie czy dodanie krawędzi spowoduje cykl :P

To tak jakby ktoś zapytał w jaki sposób "znać" sumę na każdym przedziale w tablicy. A ja mu powiem: Policz dla każdego przedziału osobno, jak już to zrobisz, to odpowiesz w czasie stałym (w końcu chcesz odpowiedzieć na to pytanie w czasie stałym). Ale mogły być tablice prefixowe, ale co tam, ważne że odpowiedziałem na pytanie

@xawery chętnie poczytam jakie lepsze rozwiązanie proponujesz :)
To moje rozwiązanie można trochę przyspieszyć stosując inteligentną kompresje ścieżki. Tzn nie bawić się w update za każdym razem, tylko zapisywać gdzieś czas ostatniej modyfikacji wierzchołka X (zaktualizowany wierzchołek leci na górę żebyśmy mieli te ostatnio zaktualizowane po kolei od najnowszego) i pamiętać w zbiorze źródeł informacje o ostatniej aktualizacji danego źródła. Teraz jeśli mamy dodać krawędź dla X to najpierw dokonujemy aktualizacji potencjalnie nieaktualnych wierzchołków (trzymamy je np. w jakiejś liście w której przerzucamy zaktualizowany wierzchołek na koniec, w efekcie nieaktualne mogą być tylko na górze) a potem sprawdzamy przynależność do źródeł.
Takie rozwiązanie powinno potencjalnie zmniejszyć liczbę koniecznych aktualizacji, bo wykonujemy je tylko kiedy trzeba.