Ders programı: bütün dersler bitirilebilir mi?

Problem

0'dan numCourses - 1'e kadar numaralı dersler var. Ön koşullar {ders, önceAlınması} çiftleri olarak veriliyor: {3, 1} "3'ü almadan önce 1'i bitirmelisin" demek. Tüm dersleri bir sıraya koyup bitirmek mümkün mü? true ya da false döndür.

numCourses = 3, ön koşullar = [{1, 0}, {2, 1}]
0 -> 1 -> 2 sırasıyla alınabilir.   Çıktı: true

numCourses = 5, ön koşullar = [{1, 0}, {2, 1}, {3, 2}, {1, 3}, {4, 0}]
1 -> 2 -> 3 -> 1 döngüsü var.       Çıktı: false

İkinci örnekte 0 ve 4 sorunsuz alınabilir; ama 1, 2 ve 3 birbirini beklediği için hiçbiri başlayamaz.

Netleştirme soruları

• Kenar yönü nedir? {a, b} "b, a'dan önce" mi? (Evet. Yönü ters kurmak döngü tespitini değiştirmez ama Course Schedule II'de sırayı ters çevirir; netleştirmek iyi alışkanlık.)
• Aynı ön koşul birden fazla kez verilebilir mi? (Verilirse çözüm bozulmamalı.)
• Bir ders kendisinin ön koşulu olabilir mi ({0, 0})?
• Ders ve kenar sayısı ne kadar? (Özyinelemeli DFS derinliği için.)

İpuçları

Yaklaşım

Problem, yönlü grafta döngü var mı sorusudur. Döngü yoksa graf bir DAG'dir ve her DAG'in en az bir topolojik sırası vardır.

Kaba çözüm: Her düğümden DFS başlatıp kendisine geri dönüp dönmediğine bakmak. O(V·(V + E)).

Kahn algoritması (BFS, seçilen çözüm): Giriş derecesi 0 olan düğümler bağımsızdır, hemen işlenebilir. Bir düğüm işlendiğinde onun çıkış kenarları grafdan "silinir", yani komşuların derecesi azalır. Döngüdeki düğümlerin derecesi hiçbir zaman 0'a düşmez, çünkü her biri döngüdeki bir başkasını bekler. Dolayısıyla işlenen düğüm sayısı numCourses'tan azsa döngü vardır. Ek avantaj: işlenme sırası geçerli bir topolojik sıradır (Course Schedule II'nin cevabı).

DFS üç renk: Her düğüm beyaz (görülmedi), gri (şu an stack'te), siyah (bitti). DFS sırasında gri bir düğüme kenar bulunursa geri kenar (back edge), yani döngü vardır. Siyah düğüme kenar döngü değildir; sık hata, tek bir visited kümesiyle "daha önce görüldü" ile "şu an yolda" durumlarını karıştırmaktır. Bu sorunun test kodunda referans çözüm olarak DFS üç renk kullanıldı.

Java çözümü

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public final class CourseSchedule {

    /** prerequisites[i] = {course, requiredFirst}: requiredFirst -> course kenarı. */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> unlocks = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) unlocks.add(new ArrayList<>());
        int[] inDegree = new int[numCourses];              // her dersin bekleyen ön koşul sayısı
        for (int[] p : prerequisites) {
            unlocks.get(p[1]).add(p[0]);
            inDegree[p[0]]++;
        }

        ArrayDeque<Integer> ready = new ArrayDeque<>();
        for (int c = 0; c < numCourses; c++) {
            if (inDegree[c] == 0) ready.offer(c);
        }

        int finished = 0;
        while (!ready.isEmpty()) {
            int course = ready.poll();
            finished++;
            for (int next : unlocks.get(course)) {
                if (--inDegree[next] == 0) ready.offer(next);   // son ön koşulu da bitti
            }
        }
        return finished == numCourses;                     // bitmeyen ders varsa döngüde kalmıştır
    }
}

Komşuluk listesi olarak List<List<Integer>> kullanıldı. Map<Integer, List<Integer>> de çalışır, ama düğümler 0..n-1 aralığında yoğun olduğu için liste daha az bellek ve kutulama (boxing) maliyeti demektir.

Karmaşıklık

• Zaman: O(V + E); V ders sayısı, E ön koşul sayısı. Graf kurulumu O(V + E), her düğüm bir kez kuyruğa girer, her kenar bir kez işlenir.
• Bellek: O(V + E) komşuluk listesi, O(V) derece dizisi ve kuyruk.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Zincir 0 -> 1 -> 2: true.
• İki düğümlü döngü: false.
• Kendine ön koşul {0, 0}: false (derece 1 olur, hiç 0'a düşmez).
• Ön koşul yok: true.
• Tekrarlanan kenar {1, 0} iki kez: true. Kenar iki kez eklenir, derece 2 olur ve 0 işlendiğinde iki kez azaltılır; tutarlıdır.
• Başlangıçtan ulaşılamayan döngü (örnek 2): false.
• Elmas (0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3): true. Tek visited kümeli hatalı DFS'in yanlışlıkla döngü sandığı yapı.
• 3.000 rastgele graf (1-8 düğüm, 0-11 kenar, self-loop ve tekrar dahil) DFS üç renk referansıyla karşılaştırıldı.

Mülakatçı için

Bu soru problemi grafa çevirme becerisini ölçer. Güçlü aday ilk iki dakikada "bu yönlü grafta döngü tespiti" der ve Kahn ile DFS arasında bilinçli seçim yapar. Elmas şekli, DFS'te "ziyaret edildi" ile "yolda" ayrımını bilmeyen adayı ortaya çıkarır; aday DFS yazarsa bu örneği dry run için ver.

İpucu zamanlaması: Graf modeline 3-4 dakikada ulaşamayan adaya ilk ipucunu ver. DFS ile tek renkli visited yazıp elmasta hata yapan adaya hatayı söyleme; dry run sırasında bulmasını bekle, bulamazsa "gri" kavramını sor.

Takip sorusu 1: Döngü varsa döngüdeki dersleri döndür. Beklenen: üç renkli DFS'te gri düğüme kenar bulunduğunda, stack'teki yolu o düğümden itibaren geri vermek; Kahn'da işlenmeyen düğümler döngüdedir ya da bir döngüyü bekliyordur (ikisini ayırt etmek gerekir).

Takip sorusu 2: Bir dönemde en fazla k ders alınabiliyor ve önkoşulsuz dersler aynı dönemde alınabilir; en az kaç dönem? Beklenen: k sınırsızsa cevap Kahn'ın katman sayısıdır (en uzun yol); k sınırlıysa problem NP-zor bir zamanlama problemine dönüşür (LeetCode 1494 küçük n için bitmask DP ile çözülür).

Takip sorusu 3: Bunu bir build sistemi ya da Spring bean bağımlılıkları için düşün. Beklenen: modül derleme sırası ve bean oluşturma sırası topolojik sıradır; Spring constructor injection'da döngüyü BeanCurrentlyInCreationException ile reddeder (Spring Boot 2.6'dan beri döngüsel referanslar varsayılan olarak yasak).

Benzer problemler

• Course Schedule II (LeetCode 210)
• Course Schedule IV (LeetCode 1462)
• Parallel Courses (LeetCode 1136)
• Alien Dictionary (LeetCode 269)
• Find Eventual Safe States (LeetCode 802)