Bagaimanakah Anda Menyelesaikan Course Schedule II dengan Topological Sort?

Gesaan dan Skop

Terdapat num_courses kursus yang dilabelkan dari 0 hingga num_courses - 1. Pasangan prasyarat [course, prerequisite] bermaksud bahawa prerequisite mesti diselesaikan sebelum course. Kembalikan sebarang susunan yang melengkapkan setiap kursus. Kembalikan senarai kosong jika tiada susunan sedemikian wujud.

Untuk versi ini, anggap 0 <= num_courses <= 2000, setiap label kursus adalah sah, pasangan adalah berbeza (unik), dan input tidak mengandungi self-edge. Kembalikan senarai kosong apabila num_courses == 0. Untuk num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]], kedua-dua [0, 1, 2, 3] dan [0, 2, 1, 3] adalah betul. Untuk [[1, 0], [0, 1]], kedua-dua kursus bergantung antara satu sama lain, jadi satu-satunya respons yang sah ialah senarai kosong.

Ini ialah masalah pengekodan kejuruteraan perisian am yang representatif. Tugas terasnya ialah menterjemahkan kebergantungan bahasa semula jadi kepada graf berarah dan menentukan sama ada graf tersebut adalah asiklik. Masalah asas meminta sebarang susunan yang sah. Ia tidak meminta susunan terkecil mengikut leksikografi, tempoh kursus, atau had ke atas kursus serentak.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah arah sisi (edge direction). [course, prerequisite] menjadi prerequisite -> course, kerana melengkapkan prasyarat membolehkan kursus diambil. Graf yang diterbalikkan mungkin masih menghasilkan kutipan susunan, tetapi susunan tersebut mengekod kekangan yang bertentangan.

Isyarat kedua ialah sama ada calon boleh menerbitkan indegree daripada frasa “kursus yang kini tersedia.” Indegree sesebuah kursus ialah bilangan prasyarat langsung yang masih belum dipenuhi. Hanya kursus dengan indegree sifar (zero-indegree) yang sedia diambil. Melengkapkan satu kursus hanya mengurangkan indegree pengganti langsungnya. Jawapan yang mantap menerangkan keadaan ini dan bukannya sekadar menyebut “gunakan BFS.”

Isyarat ketiga ialah pengesanan kitaran. Baris gilir (queue) yang kosong tidak mewajarkan pemulangan jawapan separa. Semua nod hanya diproses apabila panjang hasil bersamaan dengan bilangan kursus. Hasil yang lebih pendek bermakna subgraf yang tinggal tidak mempunyai nod ber-indegree sifar dan mesti mengandungi kitaran berarah.

Penemu duga juga akan menyemak kerumitan, sempadan, dan disiplin kontrak fungsi. Pelaksanaan adjacency-list menggunakan masa dan ruang O(V + E). deque.popleft() mengekalkan penyingkiran dari hadapan baris gilir dalam masa malar. Ujian hendaklah merangkumi pelbagai susunan yang sah, kursus yang terputus sambungan (disconnected), input kosong, dan rantai kebergantungan yang panjang.

Soalan Penjelasan Sebelum Menjawab

• Bolehkah saya mengembalikan sebarang susunan, atau adakah ia mesti terkecil mengikut leksikografi? Baris gilir biasa mengembalikan sebarang

susunan. Susunan terkecil memerlukan min-heap dan menukar batas masa kepada O(E + V log V).

• Bolehkah pasangan prasyarat berulang? Masalah ini menyatakan ia adalah berbeza. Jika ia boleh berulang, sama ada

kekalkan entri kejiranan pendua dan kira kedua-duanya dalam indegree, atau nyahduplikasi kedua-dua struktur semasa membina graf. Menyahduplikasi satu bahagian sahaja menjadikan kiraan tidak konsisten.

• Bolehkah label tidak sah, atau bolehkah input mengandungi self-edge? Masalah asas menganggap input yang

telah disahkan. API yang defensif harus membezakan permintaan tidak sah daripada graf sah yang mengandungi kitaran, dan bukannya memetakan kedua-dua kes secara senyap kepada senarai kosong.

• Adakah kita memerlukan satu susunan atau setiap susunan yang sah? Mencari satu susunan ialah traversal graf linear.

Menyenaraikan setiap susunan mencapangkan ke atas semua nod yang tersedia pada masa itu dan boleh menghasilkan keputusan yang hampir faktorial.

• Bolehkah kursus berjalan secara selari? Hasil asas ialah susunan linear. Dengan kapasiti semester

tanpa had, semester minimum memerlukan pemprosesan baris gilir tahap demi tahap. Dengan tempoh kursus, masalah ini menjadi pengiraan laluan terpanjang (longest-path) pada DAG.

• Adakah graf muat dalam memori? Adjacency list adalah mudah untuk V <= 2000. Storan

luaran atau pemprosesan berpartition akan menjadi masalah sistem yang berbeza.

Kerangka Jawapan 30 Saat

“Saya akan memodelkan setiap kursus sebagai nod dan menukar [course, prerequisite] kepada sisi berarah daripada prasyarat ke kursus. Saya juga akan mengira indegree setiap kursus. Saya meletakkan setiap kursus ber-indegree sifar ke dalam baris gilir, mengeluarkannya satu demi satu ke dalam hasil secara berulang, mengurangkan indegree penggantinya, dan memasukkan pengganti ke dalam baris gilir apabila indegree-nya menjadi sifar. Baris gilir mengandungi tepat kursus yang belum diproses yang semua prasyaratnya telah selesai, jadi setiap pilihan adalah selamat. Jika hasil mengandungi setiap kursus, saya mengembalikannya; jika tidak, nod yang tinggal mengandungi kitaran, jadi saya mengembalikan senarai kosong. Dengan adjacency list, kedua-dua masa dan ruang tambahan adalah O(V + E).”

Penyelaman Mendalam Langkah demi Langkah

Penyelesaian terus berulang kali mengimbas setiap kursus yang belum dipilih dan memilih satu yang prasyaratnya telah pun muncul. Walaupun dengan set kursus yang telah selesai, setiap pusingan mungkin memeriksa setiap sisi. Rangkaian boleh memerlukan V pusingan, menjadikan kes terburuk O(VE). Pengiraan semula kebergantungan yang telah dipenuhi secara berulang adalah kekangan utamanya (bottleneck).

Algoritma Kahn mengekalkan maklumat tersebut secara berperingkat sebagai indegree. Biarkan graph[u] mengandungi kursus yang mungkin dibuka selepas melengkapkan u, dan biarkan indegree[v] mengira prasyarat langsung v yang masih tinggal. Untuk setiap [course, prerequisite], tambahkan course ke graph[prerequisite] dan tingkatkan indegree[course].

Algoritma ini mengekalkan dua invariant:

1. indegree[v] bersamaan dengan bilangan sisi yang masuk ke v daripada nod yang belum diproses.
2. Baris gilir mengandungi semua dan hanya kursus belum diproses yang baki indegree-nya adalah sifar.

Kiraan awal memenuhi invariant pertama, dan memasukkan setiap nod ber-indegree sifar ke dalam baris gilir membentuk invariant kedua. Apabila kursus u dikeluarkan, tiada prasyarat belum diproses yang menghala ke dalamnya, jadi menambahkannya ke dalam hasil adalah selamat. Mengeluarkan u diwakili dengan melawat graph[u] dan mengurangkan indegree setiap pengganti. Pengganti dimasukkan ke baris gilir tepat apabila kiraannya mula-mula mencapai sifar, mengekalkan kedua-dua invariant.

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 kursus dikeluarkan, invariant menjamin bahawa semua prasyaratnya telah muncul lebih awal, menjadikan hasilnya sah. Jika hasil lebih pendek daripada V, setiap nod dalam subgraf terhingga yang tinggal mempunyai baki indegree positif. Mulakan pada mana-mana nod yang tinggal dan ikuti satu sisi masuk secara berulang. Graf terhingga akhirnya mesti mengulangi nod, dan segmen yang berulang tersebut ialah kitaran berarah. Oleh itu, tiada susunan lengkap wujud. Semakan panjang juga merupakan ujian kitaran.

Setiap nod masuk dan keluar dari baris gilir paling banyak sekali. Setiap sisi dikendalikan sekali semasa membina graf dan sekali semasa melepaskan pengganti, jadi masanya ialah O(V + E). Adjacency list, tatasusunan indegree, baris gilir, dan hasil menggunakan ruang O(V + E). Pelaksanaan menggunakan deque kerana list.pop(0) dalam Python mengalihkan elemen yang tinggal dan boleh menjadikan operasi baris gilir berbentuk linear.

Pengesahan adversarial harus menyemak sifat dan bukannya satu jawapan tetap. Hasil yang berjaya mesti mengandungi tepat V label unik, dan kedudukan prerequisite mestilah lebih kecil daripada kedudukan course untuk setiap pasangan. Uji graf kosong, satu nod, semua nod bebas, rantai panjang, bentuk berlian dengan pelbagai susunan, komponen terputus sambungan, dan kitaran berarah. Kes berlian mengesan ujian yang secara salah memerlukan satu susunan topologi tertentu.

DFS juga boleh mengira susunan topologi. Gunakan keadaan putih, kelabu, dan hitam; sisi ke nod kelabu mengesan kitaran, dan nod memasuki hasil pada keluar rekursif sebelum postorder diterbalikkan. DFS berguna apabila API juga mesti melaporkan kitaran konkrit, tetapi rantai yang panjang boleh melebihi had rekursi Python. Algoritma Kahn mendedahkan set kursus yang kini tersedia dan berkembang secara semula jadi kepada semester selari, menjadikannya pilihan yang lebih langsung di sini. Bagi graf yang sangat kecil di mana hanya kebolehlaksanaan yang penting, imbasan berulang boleh menjadi lebih pendek; nyatakan kos kes terburuknya dan bukannya memanggilnya linear.

Contoh Jawapan Berkualiti Tinggi

“Saya akan mengesahkan terlebih dahulu bahawa sebarang susunan yang sah boleh diterima dan menganggap label serta sisi berbeza adalah sah. Setiap pasangan [course, prerequisite] mencipta sisi daripada prasyarat ke kursus. Indegree kursus kemudiannya mengukur bilangan prasyarat langsung yang masih belum selesai.

Saya membina adjacency list dan tatasusunan indegree, kemudian menambah setiap kursus ber-indegree sifar ke dalam deque. Di dalam gelung, saya mengeluarkan kursus ke dalam jawapan dan mengurangkan indegree penggantinya. Pengganti hanya dimasukkan ke baris gilir apabila indegree-nya menjadi sifar. Invariant utamanya ialah baris gilir mengandungi tepat kursus tanpa prasyarat yang belum selesai, jadi memilih daripadanya tidak boleh melanggar mana-mana sisi.

Saya tidak boleh memulangkan hasil tanpa syarat apabila baris gilir kosong. Jika panjang jawapan sama dengan bilangan kursus, setiap kebergantungan telah dipenuhi. Jika ia lebih pendek, semua nod yang tinggal masih mempunyai sisi masuk. Mengikuti sisi masuk dalam graf terhingga pasti akan melawat semula nod, membuktikan bahawa kitaran masih wujud, jadi saya mengembalikan senarai kosong.

Adjacency list memproses setiap nod dan sisi beberapa kali malar, memberikan masa O(V + E) dan ruang O(V + E). Saya akan menguji graf kosong, satu nod, rantai panjang, berlian dengan pelbagai jawapan, komponen terputus sambungan, dan kitaran dua nod. Untuk pelbagai jawapan, saya mengesahkan kedudukan relatif setiap prasyarat dan bukannya membandingkannya dengan satu tatasusunan tetap.”

Kesilapan Biasa

• Membina course -> prerequisite → kursus mungkin muncul sebelum prasyaratnya → **Bina

prerequisite -> course, mengikut soalan “apakah yang dilepaskan setelah melengkapkan nod ini?”**

• Bermula hanya daripada kursus 0 → komponen yang terputus sambungan akan hilang → **Imbas setiap nod dan masukkan

setiap nod awal ber-indegree sifar ke dalam baris gilir.**

• Mengembalikan hasil separa apabila baris gilir kosong → input berkitar dilaporkan sebagai berjaya → **Kembalikan

susunan hanya apabila len(order) == num_courses.**

• Memasukkan nod ke baris gilir lebih daripada sekali → hasil mengandungi kursus pendua → **Masukkan ke baris gilir hanya pada

peralihan daripada indegree 1 kepada 0.**

• Menggunakan list.pop(0) sebagai baris gilir → input yang besar mengalihkan elemen berulang kali → **Gunakan

deque.popleft().**

• Membandingkan output dengan satu susunan topologi tetap → susunan sah yang lain menggagalkan ujian → **Semak

keunikan, panjang, dan kedudukan relatif setiap sisi.**

• Menyahduplikasi graf tetapi bukan indegree, atau sebaliknya → kiraan tidak sepadan di bawah kontrak sisi

pendua → Kekalkan pendua secara konsisten atau nyahduplikasi setiap sisi semasa pembinaan graf.

• Mendakwa ruang tambahan O(V) → adjacency list masih menyimpan semua sisi → **Laporkan O(V + E) untuk

perwakilan graf jarang (sparse) ini.**

• Menggunakan DFS tanpa keadaan in-progress → nod kitaran melakukan rekursi berulang kali atau selesai secara salah →

Gunakan sekurang-kurangnya tiga keadaan untuk memisahkan nod aktif dan nod yang telah selesai.

Soalan Susulan dan Cara Mengendalikannya

Susulan 1: Bagaimanakah anda mengembalikan susunan sah yang paling kecil mengikut leksikografi?

Gantikan baris gilir dengan min-heap. Mengambil label terkecil dalam kalangan semua nod yang kini tersedia memberikan hasil terkecil mengikut leksikografi melalui hujah pertukaran tamak (greedy exchange). Pemprosesan sisi kekal O(E), manakala penyisipan dan penyingkiran heap menjadikan jumlah keseluruhan O(E + V log V). Baris gilir biasa kekal lebih mudah dan pantas apabila sebarang susunan diterima.

Susulan 2: Dengan kursus selari tanpa had bagi setiap semester, apakah kiraan semester minimum?

Proses baris gilir mengikut saiz tahap semasanya. Kursus dalam satu tahap selesai dalam semester yang sama, dan pengganti ber-indegree sifar yang baru dibuka membentuk tahap seterusnya. Tingkatkan kiraan semester bagi setiap tahap. Ini hanya berfungsi apabila semua kursus mengambil masa yang sama dan kapasiti semester tidak terhad. Had sebanyak paling banyak k kursus bagi setiap semester menjadikan pemprosesan tahap mudah tidak mencukupi untuk keoptimuman global.

Susulan 3: Kursus mempunyai tempoh berbeza. Bagaimanakah anda mencari masa tamat pengajian paling awal?

Dapatkan susunan topologi terlebih dahulu, kemudian jalankan dynamic programming mengikut susunan tersebut. Waktu mula terawal bagi kursus ialah maksimum daripada masa selesai terawal dalam kalangan prasyaratnya; tambahkan tempohnya sendiri untuk mendapatkan masa selesai terawalnya. Jawapannya ialah masa selesai maksimum. Tahap Kahn tidak mencukupi kerana kursus sepuluh minggu dan kursus satu minggu tidak boleh dianggap sebagai unit yang sama.

Susulan 4: Bagaimanakah anda mengembalikan satu kitaran kebergantungan yang konkrit?

Algoritma Kahn membuktikan bahawa subgraf yang tinggal mempunyai kitaran tetapi tidak mengekalkan laluannya. Jalankan three-color DFS pada nod yang tinggal dan simpan penuding induk (parent pointers). Pada sisi ke nod kelabu, ikuti induk ke belakang untuk membina semula kitaran. Jika diagnostik merupakan keperluan utama, DFS topological sort dengan penjejakan induk boleh digunakan dari awal.

Susulan 5: Bagaimanakah anda mengekalkan susunan apabila sisi prasyarat ditambah?

Untuk kemas kini yang jarang, menjalankan semula algoritma O(V + E) selepas setiap penambahan adalah paling boleh dipercayai dan paling mudah disahkan. Bagi graf yang besar dengan kemas kini yang kerap, simpan kedudukan semasa setiap nod. Sisi yang sudah konsisten dengan susunan tersebut tidak memerlukan perubahan; sisi yang tidak konsisten memerlukan pemeriksaan ketercapaian dan penyusunan semula dalam selang yang terjejas. Penyusunan topologi dinamik adalah rumit, jadi kosnya perlu dijustifikasikan oleh saiz graf yang diukur dan kadar kemas kini.

Susulan 6: Bagaimanakah anda menyenaraikan setiap susunan kursus yang sah?

Gunakan backtracking. Pada setiap langkah, buat percabangan ke atas semua nod ber-indegree sifar semasa, pilih satu buat sementara waktu, kemas kini penggantinya, lakukan rekursi, dan pulihkan indegree-nya. Ini mengelakkan susunan yang tidak sah, tetapi bilangan susunan yang sah boleh menghampiri V!, jadi masa larian adalah sekurang-kurangnya berkadar dengan output. Sahkan had yang kecil dahulu dan tanya sama ada pemanggil benar-benar memerlukan kiraan, sampel, atau hanya k susunan yang pertama.