Course Schedule

Bir öğrencinin yapacağı gibi planla. Her turda, henüz almadığın her derse bak. Ön koşullarının tümü alınmışsa o dersi al. Bir turda hiçbir ders alınmayana kadar tekrarla. O zamana kadar tüm dersler alınmışsa yanıt doğrudur.

Hiçbir ders alınamayan bir turun neden yanlış yanıt anlamına geldiği: Böyle bir turda geriye kalan her dersin, yine geriye kalan bir ön koşulu vardır. Geride kalan herhangi bir dersten başla ve alınmamış ön koşullarından birine doğru ilerlemeyi sürdür. Adımların asla tükenmez ve ders sayısı sınırlıdır; bu yüzden daha önce ziyaret ettiğin bir derse geri dönersin. Bu bir döngüdür ve döngüdeki dersler sonsuza dek birbirini bekler.

Yöntem doğrudur, ancak her turda tüm ders çiftlerini ve tüm dersleri yeniden inceler; ayrıca bir turda yalnızca bir ders alınabilir. Her biri kendinden önceki dersi gerektiren 5,001 derslik bir zincir 5,000'den fazla tur sürer; 100,000 ders arasında bu yaklaşık 5 × 10^8 kontrol demektir ve bunların neredeyse tümü durumu değişmemiş dersler üzerinde yapılır.

Döngü, başladığı yere geri dönen bir yoldur. Derinlik öncelikli arama, o anda izlediği yolda hangi derslerin bulunduğunu hatırlayarak bir döngü bulur. Her derse üç durumdan birini verin: ziyaret edilmedi, mevcut yolda ve tamamlandı.

Bir dersten, oklarını izleyerek onu bekleyen derslere ilerleyin. Bir dersin üzerine geldiğinizde onu "yolda" olarak işaretleyin; o dersten çıkan her ok incelenip geri döndüğünüzde ise "tamamlandı" olarak işaretleyin. Yolda olan bir derse giden ok, bir daire çizdiğiniz anlamına gelir: false döndürün. Tamamlanmış bir derse giden ok güvenlidir; çünkü o dersten erişilebilen her şey kontrol edilmiş ve döngü içermediği doğrulanmıştır, bu yüzden o dersi atlayın. Her derse bir kez girilir ve her ok bir kez izlenir.

İki durum yeterli değildir. 0 → 1, 0 → 2, 1 → 3, 2 → 3 elmasında arama, 2 üzerinden 3. derse ikinci kez ulaşır; ancak o zamana kadar 3 tamamlanmıştır, yolda değildir ve döngü yoktur. Döngüyü yalnızca mevcut yola geri dönen bir ok kapatır.

Aramayı kendi yığınınızla ve her ders için incelenmemiş bir sonraki okun konumunu tutarak yazın. Özyinelemeli sürüm daha kısadır, ancak 5,000 dersten oluşan bir zincir 5,000 çağrı derinliğine ulaşır.

İlk yaklaşımdaki turlar, değişmemiş dersleri tekrar kontrol ederek zaman kaybettirir. Bir ders yalnızca tek bir anda müsait hâle gelir: son ön koşulu alındığında. Bu nedenle her ders için hâlâ kaç ön koşulunu beklediğini, yani giriş derecesini sayın. Bir dersi aldığınızda, onu bekleyen her dersin sayısını azaltın. Sayısı 0'a düşen bir ders artık müsaittir, bu yüzden onu kuyruğa eklersiniz.

Kuyruğu en baştan sayısı 0 olan tüm derslerle başlatın, sonra kuyruk boşalana kadar dersleri kuyruktan alın. İlk örnekte 0'dan 3'e kadar olan derslerin başlangıç sayıları 0, 1, 1, 1'dir. 0'ı almak, 1 numaralı dersin sayısını 0'a düşürür; 1'i almak, 2 ve 3 numaralı derslerin sayılarını 0'a düşürür; dördü de alınır, dolayısıyla yanıt true olur. Her ders kuyruğa en fazla bir kez girer ve her çift bir sayıyı bir kez azaltır, bu nedenle işlem O(V + E) olur.

Geride kalan bir dersin neden bir döngü anlamına geldiği: a dersi alınmamışken kuyruk boşalırsa, sayısı 0'dan büyüktür; dolayısıyla ön koşullarından biri olan b dersi de alınmamıştır. Aynı durum b için de geçerlidir ve böyle devam eder. Bir dersten alınmamış bir ön koşula doğru ilerleyen yol hiç sona ermez; dolayısıyla bir dersi yeniden ziyaret eder ve bu bir döngüdür. İkinci örnekte başlangıçta hiçbir sayım 0 değildir, kuyruk boştur ve üç dersin hiçbiri alınmaz.

Tersi de geçerlidir: Bir döngüdeki ders, aynı döngüdeki başka bir dersi bekler; bu nedenle o ders alınmadan önce sayısı 0'a ulaşamaz ve bu derslerin hiçbiri ilk alınan olamaz. Dolayısıyla "her dersin alınması" ve "döngü olmaması" aynı şeydir. Ek bir avantaj olarak, derslerin kuyruktan çıkış sırası geçerli bir programdır.