Course Schedule

Zapla­­nuj to tak, jak zrobiłby to uczeń. W każdej rundzie sprawdź każdy kurs, którego jeszcze nie ukończyłeś. Jeśli wszystkie jego wymagania wstępne są spełnione, ukończ go. Powtarzaj, aż w którejś rundzie nie ukończysz żadnego kursu. Jeśli do tego czasu ukończysz wszystkie kursy, odpowiedź brzmi true.

Dlaczego runda, w której nie udało się ukończyć żadnego kursu, oznacza false: każdy pozostały kurs ma wymaganie wstępne, które również nie zostało spełnione. Zacznij od dowolnego pozostałego kursu i za każdym razem przechodź do jednego z jego niespełnionych wymagań wstępnych. Nie zabraknie Ci kolejnych kroków, a kursów jest tylko określona liczba, więc wrócisz do kursu, który już odwiedziłeś. To cykl, a kursy w nim będą na siebie czekać bez końca.

Ta metoda jest poprawna, ale w każdej rundzie ponownie sprawdza każdą parę i każdy kurs, a w jednej rundzie można ukończyć zaledwie jeden kurs. Łańcuch 5,001 kursów, z których każdy wymaga ukończenia poprzedniego, zajmuje ponad 5,000 rund; wśród 100,000 kursów to około 5 × 10^8 sprawdzeń, z których prawie wszystkie dotyczą kursów, których status się nie zmienił.

Cykl to ścieżka, która wraca do miejsca, w którym się zaczęła. Wyszukiwanie w głąb znajduje cykl, zapamiętując, które kursy znajdują się na aktualnie przemierzanej ścieżce. Przypisz każdemu kursowi jeden z trzech stanów: nieodwiedzony, na bieżącej ścieżce i ukończony.

Przechodź od kursu wzdłuż jego strzałek do kursów, które na niego czekają. Oznacz kurs jako „na ścieżce”, gdy na niego wejdziesz, a jako „ukończony”, gdy sprawdzisz wszystkie wychodzące z niego strzałki i wrócisz. Strzałka prowadząca do kursu znajdującego się na ścieżce oznacza, że zatoczyłeś krąg: zwróć false. Strzałka prowadząca do ukończonego kursu jest bezpieczna, ponieważ sprawdzono już wszystko, co jest z niego osiągalne, i nie ma tam cyklu, więc ją pomijasz. Każdy kurs jest odwiedzany raz, a każda strzałka jest śledzona raz.

Dwa stany nie wystarczą. W rombie 0 → 1, 0 → 2, 1 → 3, 2 → 3 wyszukiwanie dociera do kursu 3 po raz drugi przez 2, ale do tego czasu kurs 3 jest już ukończony, a nie znajduje się na ścieżce, więc nie ma cyklu. Tylko strzałka prowadząca z powrotem na bieżącą ścieżkę zamyka pętlę.

Zapisz wyszukiwanie, używając własnego stosu oraz pozycji następnej niezbadanej strzałki dla każdego kursu. Wersja rekurencyjna jest krótsza, ale łańcuch 5,000 kursów wymagałby 5,000 wywołań w głąb.

Rundy w pierwszym podejściu marnują czas na ponowne sprawdzanie kursów, które się nie zmieniły. Kurs staje się dostępny tylko w jednym momencie: gdy zostanie zaliczone jego ostatnie wymaganie wstępne. Dlatego policz, na ile wymagań wstępnych każdy kurs nadal czeka — to jego stopień wejściowy. Gdy zaliczasz kurs, zmniejsz licznik każdego kursu, który na niego czeka. Gdy licznik spadnie do 0, oznacza to, że kurs jest już dostępny, więc dodajesz go do kolejki.

Na początku umieść w kolejce wszystkie kursy, których licznik wynosi 0, a potem pobieraj z niej kursy, aż będzie pusta. W pierwszym przykładzie początkowe liczniki dla kursów od 0 do 3 wynoszą 0, 1, 1, 1. Zaliczenie kursu 0 zmniejsza licznik kursu 1 do 0; zaliczenie kursu 1 zmniejsza liczniki kursów 2 i 3 do 0; wszystkie cztery kursy zostają zaliczone, więc odpowiedzią jest true. Każdy kurs trafia do kolejki co najwyżej raz, a każda para zmniejsza jeden licznik raz, więc złożoność wynosi O(V + E).

Dlaczego pozostawiony kurs oznacza cykl: jeśli kolejka się opróżni, zanim kurs a zostanie zaliczony, jego licznik jest większy od 0, więc jedno z jego wymagań wstępnych, b, również nie zostało zaliczone. To samo dotyczy kursu b i tak dalej. Przechodząc od kursu do niezliczonego wymagania wstępnego, nigdy się nie zatrzymasz, więc w końcu trafisz ponownie na ten sam kurs, co oznacza cykl. W drugim przykładzie początkowy licznik żadnego kursu nie wynosi 0, kolejka jest więc pusta, a żaden z trzech kursów nie zostaje zaliczony.

W drugą stronę działa to tak samo: kurs należący do cyklu czeka na inny kurs z tego samego cyklu, więc jego licznik nie może spaść do 0, zanim tamten kurs nie zostanie zaliczony, a żaden z nich nie zostanie zaliczony jako pierwszy. A zatem „wszystkie kursy zostały zaliczone” i „nie ma cyklu” oznaczają to samo. Dodatkową korzyścią jest to, że kolejność, w jakiej kursy opuszczają kolejkę, stanowi prawidłowy harmonogram.