Bagaimana Cara Menyelesaikan Course Schedule II dengan Topological Sort?

Prompt dan Cakupan Masalah

Terdapat num_courses mata kuliah yang diberi label dari 0 hingga num_courses - 1. Pasangan prasyarat [course, prerequisite] berarti prerequisite harus diselesaikan sebelum course. Kembalikan urutan apa pun yang menyelesaikan setiap mata kuliah. Kembalikan daftar kosong jika tidak ada urutan yang memungkinkan.

Untuk versi ini, asumsikan 0 <= num_courses <= 2000, setiap label mata kuliah valid, pasangan-pasangan tersebut berbeda (unik), dan input tidak mengandung self-edge. Kembalikan daftar kosong jika num_courses == 0. Untuk num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]], baik [0, 1, 2, 3] maupun [0, 2, 1, 3] adalah benar. Untuk [[1, 0], [0, 1]], kedua mata kuliah saling bergantung satu sama lain, sehingga satu-satunya respons yang valid adalah daftar kosong.

Ini adalah masalah coding rekayasa perangkat lunak umum yang representatif. Tugas utamanya adalah menerjemahkan dependensi bahasa alami ke dalam graf berarah dan menentukan apakah graf tersebut asiklik (acyclic). Masalah dasar ini meminta urutan valid apa pun. Masalah ini tidak meminta urutan terkecil secara leksikografis, durasi mata kuliah, atau batasan jumlah mata kuliah konkuren.

Apa yang Dinilai oleh Pewawancara

Sinyal pertama adalah arah tepi (edge direction). [course, prerequisite] menjadi prerequisite -> course, karena menyelesaikan prasyarat akan membuka mata kuliah tersebut. Graf yang dibalik mungkin masih menghasilkan permutasi, tetapi permutasi tersebut mengodekan batasan yang berlawanan.

Sinyal kedua adalah apakah kandidat dapat menurunkan konsep indegree dari frasa “mata kuliah yang saat ini tersedia.” Indegree suatu mata kuliah adalah jumlah prasyarat langsung yang belum terpenuhi. Hanya mata kuliah dengan zero-indegree (derajat masuk nol) yang siap diambil. Menyelesaikan satu mata kuliah hanya mengurangi indegree dari suksesor langsungnya. Jawaban yang kuat menjelaskan status ini alih-alih hanya mengatakan “gunakan BFS.”

Sinyal ketiga adalah deteksi siklus (cycle detection). Antrean yang kosong tidak membenarkan pengembalian jawaban parsial. Semua simpul (node) hanya diproses jika panjang hasil sama dengan jumlah mata kuliah. Hasil yang lebih pendek berarti bahwa subgraf yang tersisa tidak memiliki simpul ber-indegree nol dan pasti mengandung siklus berarah.

Pewawancara juga akan memeriksa kompleksitas, batas nilai (boundary), dan disiplin kontrak fungsi. Implementasi adjacency-list menggunakan waktu dan ruang O(V + E). deque.popleft() menjaga operasi penghapusan dari depan antrean tetap berwaktu konstan. Kasus uji harus mencakup beberapa urutan valid, mata kuliah yang terputus (disconnected), input kosong, dan rantai dependensi yang panjang.

Pertanyaan Klarifikasi Sebelum Menjawab

• Bolehkah saya mengembalikan urutan apa pun, atau harus yang terkecil secara leksikografis? Antrean biasa mengembalikan urutan

apa pun. Urutan terkecil membutuhkan min-heap dan mengubah batas waktu menjadi O(E + V log V).

• Bisakah pasangan prasyarat berulang? Masalah ini menyatakan pasangannya unik. Jika bisa berulang, pilihannya adalah

mempertahankan entri ketetanggaan duplikat dan menghitung keduanya dalam indegree, atau menduplikasi kedua struktur saat membangun graf. Menghapus duplikasi hanya pada satu sisi akan membuat penghitungan tidak konsisten.

• Bisakah label tidak valid, atau bisakah input mengandung self-edge? Masalah dasar mengasumsikan input yang telah

divalidasi. API yang defensif harus membedakan permintaan tidak valid dari graf valid yang mengandung siklus, alih-alih memetakan kedua kasus secara diam-diam ke daftar kosong.

• Apakah kita memerlukan satu urutan atau semua urutan yang valid? Menemukan satu urutan adalah traversal graf linear.

Menghitung setiap urutan akan mencabangkan semua simpul yang saat ini tersedia dan dapat menghasilkan hasil yang banyaknya mendekati faktorial.

• Bisakah mata kuliah diambil secara paralel? Hasil dasar adalah urutan linear. Dengan kapasitas semester yang tidak

terbatas, jumlah semester minimum memerlukan pemrosesan antrean level demi level. Dengan durasi mata kuliah, masalahnya menjadi komputasi jalur terpanjang (longest-path) pada DAG.

• Apakah graf muat di memori? Adjacency list sangat mudah untuk V <= 2000. Penyimpanan

eksternal atau pemrosesan terpartisi akan menjadi masalah sistem yang berbeda.

Kerangka Jawaban 30 Detik

“Saya akan memodelkan setiap mata kuliah sebagai simpul dan mengubah [course, prerequisite] menjadi tepi berarah dari prasyarat ke mata kuliah. Saya juga akan menghitung indegree setiap mata kuliah. Saya memasukkan setiap mata kuliah ber-indegree nol ke dalam antrean, berulang kali mengeluarkan satu ke dalam hasil, mengurangi indegree suksesornya, dan memasukkan suksesor ke antrean ketika indegree-nya menjadi nol. Antrean berisi tepat mata kuliah yang belum diproses yang semua prasyaratnya telah selesai, sehingga setiap pilihan aman. Jika hasil berisi setiap mata kuliah, saya mengembalikannya; jika tidak, simpul yang tersisa mengandung siklus, jadi saya mengembalikan daftar kosong. Dengan adjacency list, waktu dan ruang tambahannya adalah O(V + E).”

Pembahasan Mendalam Langkah demi Langkah

Solusi langsung memindai setiap mata kuliah yang belum dipilih secara berulang dan memilih salah satu yang prasyaratnya telah muncul sebelumnya. Bahkan dengan set mata kuliah yang sudah selesai, setiap putaran dapat memeriksa setiap tepi. Sebuah rantai dapat membutuhkan V putaran, menjadikan kasus terburuknya O(VE). Komputasi ulang berulang dari dependensi yang telah terpenuhi adalah bottleneck-nya.

Algoritma Kahn mempertahankan informasi tersebut secara inkremental sebagai indegree. Misalkan graph[u] berisi mata kuliah yang dapat dibuka setelah menyelesaikan u, dan misalkan indegree[v] menghitung prasyarat langsung dari v yang masih tersisa. Untuk setiap [course, prerequisite], tambahkan course ke graph[prerequisite] dan naikkan (increment) indegree[course].

Algoritma ini mempertahankan dua invarian:

1. indegree[v] sama dengan jumlah tepi yang masuk ke v dari simpul yang belum diproses.
2. Antrean berisi semua dan hanya mata kuliah yang belum diproses yang indegree tersisanya adalah nol.

Hitungan awal memenuhi invarian pertama, dan memasukkan setiap simpul ber-indegree nol ke antrean menetapkan invarian kedua. Ketika mata kuliah u dikeluarkan, tidak ada prasyarat yang belum diproses yang mengarah ke sana, sehingga menambahkannya ke hasil adalah aman. Mengeluarkan u direpresentasikan dengan mengunjungi graph[u] dan mengurangi indegree setiap suksesor. Suksesor dimasukkan ke antrean tepat saat hitungannya pertama kali mencapai nol, sehingga menjaga kedua invarian.

from collections import deque


def find_course_order(
    num_courses: int,
    prerequisites: list[list[int]],
) -> list[int]:
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        indegree[course] += 1

    ready = deque(
        course for course, degree in enumerate(indegree) if degree == 0
    )
    order: list[int] = []

    while ready:
        course = ready.popleft()
        order.append(course)

        for dependent in graph[course]:
            indegree[dependent] -= 1
            if indegree[dependent] == 0:
                ready.append(dependent)

    return order if len(order) == num_courses else []

Jika setiap mata kuliah dikeluarkan, invarian menjamin bahwa semua prasyaratnya telah muncul lebih awal, sehingga hasilnya valid. Jika hasilnya lebih pendek dari V, setiap simpul dalam subgraf hingga yang tersisa memiliki sisa indegree positif. Mulai dari simpul mana pun yang tersisa dan telusuri satu tepi masuk secara berulang. Graf hingga pada akhirnya harus mengulang suatu simpul, dan segmen yang berulang tersebut adalah siklus berarah. Oleh karena itu tidak ada urutan lengkap yang ada. Pemeriksaan panjang juga berfungsi sebagai uji siklus.

Setiap simpul masuk dan keluar antrean paling banyak satu kali. Setiap tepi ditangani satu kali saat membangun graf dan satu kali saat melepaskan suksesor, sehingga waktunya adalah O(V + E). Adjacency list, array indegree, antrean, dan hasil menggunakan ruang O(V + E). Implementasi menggunakan deque karena metode list.pop(0) pada Python menggeser elemen yang tersisa dan dapat membuat operasi antrean menjadi linear.

Validasi adversarial harus memeriksa properti alih-alih satu jawaban tetap. Hasil yang berhasil harus berisi tepat V label unik, dan posisi prerequisite harus lebih kecil dari posisi course untuk setiap pasangan. Cakup graf kosong, satu simpul, simpul yang semuanya independen, rantai panjang, bentuk diamond dengan beberapa kemungkinan urutan, komponen yang terputus, dan siklus berarah. Kasus diamond menangkap tes yang secara keliru mengharuskan satu urutan topologis tertentu.

DFS juga dapat menghitung urutan topologis. Gunakan status putih, abu-abu, dan hitam; tepi ke simpul abu-abu mendeteksi siklus, dan simpul masuk ke hasil saat keluar dari rekursi sebelum postorder dibalik. DFS berguna saat API juga harus melaporkan siklus konkret, tetapi rantai panjang dapat melebihi batas rekursi Python. Algoritma Kahn mengekspos set mata kuliah yang saat ini tersedia dan dapat diperluas secara alami ke semester paralel, menjadikannya pilihan yang lebih langsung di sini. Untuk graf sangat kecil di mana hanya kelayakan yang penting, pemindaian berulang bisa lebih pendek; sebutkan biaya kasus terburuknya alih-alih menyebutnya linear.

Contoh Jawaban Berkualitas Tinggi

“Pertama-tama saya akan mengonfirmasi bahwa urutan valid apa pun dapat diterima dan mengasumsikan label serta tepi yang berbeda adalah valid. Setiap pasangan [course, prerequisite] membuat tepi dari prasyarat ke mata kuliah. Indegree suatu mata kuliah kemudian mengukur berapa banyak prasyarat langsung yang masih belum selesai.

Saya membangun adjacency list dan array indegree, lalu menambahkan setiap mata kuliah ber-indegree nol ke deque. Di dalam loop, saya mengeluarkan mata kuliah ke dalam jawaban dan mengurangi indegree dari suksesornya. Suksesor hanya dimasukkan ke antrean ketika indegree-nya menjadi nol. Invarian kuncinya adalah antrean berisi tepat mata kuliah tanpa prasyarat yang belum selesai, jadi memilih dari antrean tidak akan melanggar tepi mana pun.

Saya tidak bisa mengembalikan hasil tanpa syarat saat antrean kosong. Jika panjang jawaban sama dengan jumlah mata kuliah, setiap dependensi telah terpenuhi. Jika lebih pendek, semua simpul yang tersisa masih memiliki tepi masuk. Mengikuti tepi masuk dalam graf hingga pasti akan mengunjungi kembali simpul yang sama, yang membuktikan bahwa siklus masih ada, jadi saya mengembalikan daftar kosong.

Adjacency list memproses setiap simpul dan tepi dalam jumlah konstan, menghasilkan waktu O(V + E) dan ruang O(V + E). Saya akan menguji graf kosong, satu simpul, rantai panjang, diamond dengan banyak jawaban, komponen terputus, dan siklus dua simpul. Untuk banyak jawaban, saya memvalidasi posisi relatif setiap prasyarat alih-alih membandingkannya dengan satu array tetap.”

Kesalahan Umum

• Membangun course -> prerequisite → mata kuliah dapat muncul sebelum prasyaratnya → **Bangun

prerequisite -> course, mengikuti pertanyaan “apa yang dibuka setelah menyelesaikan simpul ini?”**

• Hanya mulai dari mata kuliah 0 → komponen yang terputus akan hilang → **Pindai setiap simpul dan masukkan

setiap simpul awal yang ber-indegree nol ke antrean.**

• Mengembalikan hasil parsial saat antrean kosong → input yang bersiklus dilaporkan berhasil → **Kembalikan

urutan hanya jika len(order) == num_courses.**

• Memasukkan simpul ke antrean lebih dari sekali → hasil berisi mata kuliah duplikat → **Masukkan ke antrean hanya pada

transisi dari indegree 1 ke 0.**

• Menggunakan list.pop(0) sebagai antrean → input besar menggeser elemen berulang kali → **Gunakan

deque.popleft().**

• Membandingkan output dengan satu urutan topologis tetap → urutan valid lainnya menggagalkan tes → **Periksa

keunikan, panjang, dan posisi relatif setiap tepi.**

• Menghapus duplikasi pada graf tetapi tidak pada indegree, atau sebaliknya → hitungan tidak sesuai dalam kontrak tepi

duplikat → Pertahankan duplikat secara konsisten atau hapus duplikasi setiap tepi saat membangun graf.

• Mengklaim ruang ekstra O(V) → adjacency list tetap menyimpan semua tepi → **Laporkan O(V + E) untuk

representasi graf renggang (sparse) ini.**

• Menggunakan DFS tanpa status in-progress → simpul dalam siklus berekursi berulang kali atau selesai secara tidak tepat →

Gunakan setidaknya tiga status untuk memisahkan simpul aktif dan simpul yang selesai.

Pertanyaan Lanjutan dan Cara Menanganinya

Lanjutan 1: Bagaimana cara mengembalikan urutan valid yang terkecil secara leksikografis?

Ganti antrean dengan min-heap. Mengambil label terkecil di antara semua simpul yang saat ini tersedia menghasilkan hasil terkecil secara leksikografis melalui argumen greedy exchange. Pemrosesan tepi tetap O(E), sementara penyisipan dan penghapusan heap menjadikan totalnya O(E + V log V). Antrean biasa tetap lebih sederhana dan lebih cepat ketika urutan apa pun dapat diterima.

Lanjutan 2: Dengan mata kuliah paralel tanpa batas per semester, berapakah jumlah semester minimum?

Proses antrean berdasarkan ukuran level saat ini. Mata kuliah dalam satu level diselesaikan dalam semester yang sama, dan suksesor ber-indegree nol yang baru dibuka membentuk level berikutnya. Naikkan hitungan semester per level. Ini hanya berfungsi jika semua mata kuliah membutuhkan waktu yang sama dan kapasitas semester tidak terbatas. Batasan paling banyak k mata kuliah per semester membuat pemrosesan level sederhana tidak cukup untuk mencapai optimalitas global.

Lanjutan 3: Mata kuliah memiliki durasi berbeda. Bagaimana cara menemukan waktu kelulusan paling awal?

Pertama-tama dapatkan urutan topologis, kemudian jalankan dynamic programming dalam urutan tersebut. Waktu mulai paling awal suatu mata kuliah adalah maksimum dari waktu selesai paling awal di antara prasyaratnya; tambahkan durasinya sendiri untuk mendapatkan waktu selesai paling awal. Jawabannya adalah waktu selesai maksimum. Level Kahn tidak cukup karena mata kuliah sepuluh minggu dan mata kuliah satu minggu tidak dapat diperlakukan sebagai unit yang setara.

Lanjutan 4: Bagaimana cara mengembalikan satu siklus dependensi konkret?

Algoritma Kahn membuktikan bahwa subgraf yang tersisa memiliki siklus tetapi tidak menyimpan jalurnya. Jalankan three-color DFS pada simpul yang tersisa dan simpan penunjuk induk (parent pointers). Pada tepi ke simpul abu-abu, telusuri induk ke belakang untuk merekonstruksi siklus. Jika diagnostik adalah persyaratan utama, DFS topological sort dengan pelacakan induk dapat digunakan sejak awal.

Lanjutan 5: Bagaimana cara mempertahankan urutan saat tepi prasyarat ditambahkan?

Untuk pembaruan yang jarang, menjalankan ulang algoritma O(V + E) setelah setiap penambahan adalah cara paling andal dan paling mudah diverifikasi. Untuk graf besar dengan pembaruan yang sering, simpan posisi setiap simpul saat ini. Tepi yang sudah konsisten dengan urutan tersebut tidak memerlukan perubahan; tepi yang tidak konsisten memerlukan pemeriksaan keterjangkauan (reachability) dan penyusunan ulang dalam interval yang terpengaruh. Topological ordering dinamis sangat kompleks, jadi biayanya harus dijustifikasi oleh ukuran graf yang terukur dan laju pembaruan.

Lanjutan 6: Bagaimana cara mendaftar setiap urutan mata kuliah yang valid?

Gunakan backtracking. Pada setiap langkah, lakukan percabangan ke semua simpul ber-indegree nol saat ini, pilih satu untuk sementara, perbarui suksesornya, lakukan rekursi, dan pulihkan indegree-nya. Ini menghindari permutasi yang tidak valid, tetapi jumlah urutan yang valid dapat mendekati V!, sehingga waktu eksekusi setidaknya sebanding dengan output. Konfirmasikan batasan kecil terlebih dahulu dan tanyakan apakah pemanggil benar-benar membutuhkan hitungan total, sampel, atau hanya k urutan pertama.