0Pricing
DSA Interview Prep · Pelajaran

Course Schedule I dan II

Modelkan prasyarat mata kuliah sebagai graf berarah dan gunakan pengurutan topologis untuk menentukan apakah semua mata kuliah dapat diselesaikan serta urutannya

Course Schedule I dan II adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Gambaran Umum Masalah

Jadwal Mata Kuliah I (LeetCode 207): diberikan n mata kuliah dan daftar pasangan prerequisites [a, b] yang berarti 'b harus diambil sebelum a', tentukan apakah Anda dapat menyelesaikan semua mata kuliah. Jadwal Mata Kuliah II (LeetCode 210): kembalikan urutan sebenarnya untuk mengambil mata kuliah, atau larik kosong jika tidak memungkinkan. Keduanya dapat direduksi menjadi pengurutan topologis pada graf berarah yang sisi-sisinya merepresentasikan prasyarat.

Pemodelan Graf

Bangun graf berarah: untuk setiap pasangan prasyarat [a, b], tambahkan sisi b → a ('b harus muncul sebelum a' berarti b mengarah ke a). Hitung derajat masuk untuk setiap mata kuliah. Mata kuliah dengan derajat masuk 0 tidak memiliki prasyarat dan dapat langsung diambil. Masalah ini dapat diselesaikan jika dan hanya jika tidak ada siklus dalam graf tersebut (tidak ada dependensi melingkar).

from collections import defaultdict

def build_graph(n, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * n
    for a, b in prerequisites:  # b must come before a
        graph[b].append(a)
        in_degree[a] += 1
    return graph, in_degree

graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind)   # [0, 1, 1, 2]
print('Graph edges:', dict(graph))

Jadwal Mata Kuliah I: Solusi Algoritme Kahn

Gunakan algoritme Kahn. Jika jumlah mata kuliah yang diproses sama dengan n, semua mata kuliah dapat diselesaikan. Jika tidak, dependensi melingkar menghalangi penyelesaian.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    
    while queue:
        course = queue.popleft()
        count += 1
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))        # True
print(canFinish(2, [[1,0],[0,1]])) # False

Jadwal Mata Kuliah II: Mengembalikan Urutan

Sama seperti Jadwal Mata Kuliah I, tetapi kumpulkan urutan mata kuliah saat kita memprosesnya. Kembalikan urutan tersebut jika semua mata kuliah tercakup; jika tidak, kembalikan daftar kosong.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    
    while queue:
        course = queue.popleft()
        order.append(course)
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

Jadwal Mata Kuliah dengan DFS

Alternatifnya adalah menggunakan deteksi siklus DFS. Mata kuliah memiliki tiga status: belum dikunjungi (0), sedang diproses (1), selesai (2). Jika kita mencapai mata kuliah yang sedang diproses selama DFS, berarti terdapat siklus. Pendekatan ini secara fungsional setara dengan algoritme Kahn, tetapi menggunakan DFS rekursif.

from collections import defaultdict

def canFinish_dfs(numCourses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)
    
    # 0=unvisited, 1=in-progress, 2=done
    state = [0] * numCourses
    
    def has_cycle(course):
        if state[course] == 1: return True  # back edge
        if state[course] == 2: return False # already cleared
        state[course] = 1
        for nxt in graph[course]:
            if has_cycle(nxt):
                return True
        state[course] = 2
        return False
    
    return not any(has_cycle(i) for i in range(numCourses))

print(canFinish_dfs(2, [[1,0]]))        # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # False

Mengapa Arah Sisi Penting

Kesalahan umum adalah membalik arah sisi: jika prasyaratnya adalah [a, b] yang berarti 'b sebelum a', tambahkan sisi b → a, bukan a → b. Arah sisi harus mencerminkan aliran dependensi: panah menunjuk dari sesuatu yang harus dikerjakan terlebih dahulu ke sesuatu yang bergantung padanya. Dengan arah yang salah, deteksi siklus dan pengurutan akan terbalik, sehingga menghasilkan keluaran yang salah pada masalah dengan banyak dependensi.

Jadwal Mata Kuliah III: Varian Greedy

Jadwal Mata Kuliah III (LeetCode 630) adalah masalah yang berbeda: mata kuliah memiliki durasi dan batas waktu, dan Anda ingin memaksimalkan jumlah mata kuliah yang diambil. Masalah ini diselesaikan secara greedy dengan tumpukan-maks: selalu ambil mata kuliah dengan batas waktu paling akhir terlebih dahulu; jika penambahan suatu mata kuliah melampaui batas waktunya, ganti mata kuliah tersebut dengan mata kuliah terlama yang telah diambil sejauh ini (jika mata kuliah itu lebih lama). Ini adalah masalah greedy, bukan masalah pengurutan topologis—yang menunjukkan pentingnya membaca pernyataan masalah dengan cermat.

Menangani Simpul Terisolasi

Mata kuliah tanpa prasyarat dan tanpa mata kuliah yang bergantung padanya adalah simpul terisolasi—simpul tersebut memiliki derajat masuk 0 dan tidak memiliki sisi keluar. Algoritme Kahn menanganinya dengan benar: simpul-simpul tersebut langsung dimasukkan ke antrean dan diproses. Pastikan untuk menginisialisasi derajat masuk untuk ALL simpul dari 0 hingga n-1, termasuk yang tidak muncul dalam daftar prasyarat, atau simpul-simpul tersebut akan terlewat.

# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict

def findOrder_isolated(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses  # initialise ALL nodes
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        c = queue.popleft(); order.append(c)
        for nxt in graph[c]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    return order if len(order) == numCourses else []

print(findOrder_isolated(4, [[1,0]]))  # [0,1,2,3] or [2,3,0,1] etc.

Waktu Penyelesaian Mata Kuliah secara Paralel

Mata Kuliah Paralel II: temukan jumlah semester minimum untuk mengambil semua mata kuliah ketika paling banyak k mata kuliah diperbolehkan per semester dan semua prasyarat harus dipenuhi. Hal ini memerlukan pemrosesan algoritme Kahn tingkat demi tingkat dengan DP bermasker-bit untuk batasan pemilihan k—masalah yang jauh lebih sulit karena menggabungkan pengurutan topologis dengan DP bermasker-bit.

Strategi Komunikasi dalam Wawancara

Saat menghadapi masalah jenis Jadwal Mata Kuliah dalam wawancara: (1) Identifikasi masalah tersebut segera sebagai masalah pengurutan topologis / deteksi siklus. (2) Modelkan graf dengan memperjelas arah setiap sisi. (3) Pilih algoritme Kahn (BFS) untuk kesederhanaan atau DFS karena lebih familiar. (4) Tangani kasus siklus secara eksplisit. (5) Sebutkan kompleksitas waktu O(V+E). Pendekatan terstruktur ini menunjukkan kemampuan pemecahan masalah yang sistematis.

Uji Komprehensif

Menguji kedua solusi pada berbagai masukan untuk memverifikasi kebenarannya. Pendekatan algoritme Kahn menangani beberapa kemungkinan urutan dengan baik—urutan topologis valid apa pun dapat diterima sebagai jawaban untuk Jadwal Mata Kuliah II.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        c = queue.popleft(); order.append(c)
        for nxt in graph[c]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    return order if len(order) == numCourses else []

print(findOrder(1, []))                    # [0]
print(findOrder(2, [[0,1]]))              # [1, 0]
print(findOrder(3, [[1,0],[2,1]]))        # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]]))        # [] cycle

Pemeriksaan Singkat

Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.

Rangkuman Pelajaran

Dalam pelajaran ini Anda telah mempelajari: Jadwal Mata Kuliah I dan II sama-sama menggunakan pengurutan topologis dengan sisi b → a untuk prasyarat [a, b], Jadwal Mata Kuliah I hanya memeriksa len(order) == n, sedangkan Jadwal Mata Kuliah II mengembalikan urutannya, dan deteksi siklus berbasis DFS dengan tiga status merupakan alternatif yang valid untuk pendekatan BFS algoritme Kahn. Selanjutnya, kita akan mempelajari algoritme Kosaraju untuk Komponen Terhubung Kuat.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Course Schedule I dan II” gratis?

Ya — teks lengkap “Course Schedule I dan II” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Course Schedule I dan II”?

Modelkan prasyarat mata kuliah sebagai graf berarah dan gunakan pengurutan topologis untuk menentukan apakah semua mata kuliah dapat diselesaikan serta urutannya Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?

Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Course Schedule I dan II” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Algoritma Kahn: Pengurutan Topologis BFS
  2. Pengurutan Topologis DFS Pascaurutan
  3. Course Schedule I dan II
  4. Komponen Terhubung Kuat dengan Kosaraju
← Kembali ke DSA Interview Prep