Course Schedule
Ada numCourses kursus, bernomor 0 hingga numCourses-1. Setiap pasangan [a, b] dalam prerequisites berarti kamu harus menyelesaikan kursus b sebelum memulai kursus a. Kembalikan true jika ada urutan yang memungkinkanmu menyelesaikan setiap kursus, dan false jika tidak ada.
Fungsi
- numCoursesinteger
- jumlah kursus
- prerequisitesinteger-2d-array
- pasangan [a, b], masing-masing berarti kursus b harus diambil sebelum kursus a
- Mengembalikanboolean
- true jika setiap kursus dapat diselesaikan, false jika tidak
Batasan
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Setiap pasangan
[a, b]memiliki0 ≤ a, b < numCourses. - Tidak ada pasangan yang muncul dua kali.
- Sebuah pasangan dapat menyebut kursus yang sama dua kali,
[a, a]. Kursus itu memerlukan dirinya sendiri terlebih dahulu, jadi kursus itu tidak akan pernah bisa diambil.
Contoh
- Input
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Output
- true
- Penjelasan
- Kursus 0 tidak memiliki prasyarat, jadi kamu mengambilnya terlebih dahulu. Itu membebaskan kursus 1, yang membebaskan 2 dan 3, jadi urutan 0, 1, 2, 3 bisa digunakan.
- Input
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Output
- false
- Penjelasan
- Kursus 0 menunggu 2, 2 menunggu 1, dan 1 menunggu 0. Ketiganya saling menunggu dalam perulangan, jadi tidak ada yang bisa mulai lebih dulu.
Pertanyaan lanjutan
Berapa semester paling sedikit yang diperlukan untuk mencakup semua kursus, jika jumlah kursus berapa pun dapat diambil dalam satu semester selama prasyarat setiap kursus telah diselesaikan pada semester sebelumnya?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Gambarkan setiap kursus sebagai titik dan setiap pasangan
[a, b]sebagai panah daribkea. Bentuk apa pada gambar itu yang akan membuatmu tidak mungkin menyelesaikannya?Perulangan panah. Setiap kursus dalam suatu perulangan menunggu kursus lain dalam perulangan yang sama, jadi tidak ada yang bisa memulai lebih dulu. Pertanyaannya adalah apakah graf memiliki siklus.
Hitung jumlah prasyarat yang masih menunggu untuk setiap kursus. Mulai antrean dengan kursus yang jumlahnya 0, lalu setiap kali kamu mengambil satu kursus, kurangi jumlah untuk setiap kursus yang menunggunya. Jika kurang dari
numCourseskursus yang pernah masuk ke antrean, berarti ada siklus.
Solusi
Gambarkan panah b → a untuk setiap pasangan [a, b]. Setiap kursus dapat diselesaikan tepat ketika graf ini, dengan V = numCourses simpul dan E = prerequisites.length panah, tidak memiliki siklus. Algoritma Kahn memeriksanya seperti cara seorang siswa membuat rencana: terus ambil kursus yang prasyaratnya sudah selesai, lalu lihat apakah semua kursus berhasil diambil.
Ikuti setiap kursus gratis, babak demi babak
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Di setiap putaran, ambil semua kursus yang belum diambil dan semua prasyaratnya sudah diambil. Berhenti saat tidak ada yang diambil dalam satu putaran, lalu jawab true jika semua kursus sudah diambil. Tidak ada kursus yang diambil dalam satu putaran hanya jika setiap kursus yang tersisa menunggu kursus lain yang juga tersisa, yang berarti ada siklus.
Setiap putaran membaca ulang setiap pasangan dan setiap kursus, tetapi mungkin hanya mengambil satu kursus. Rantai yang terdiri dari 5,001 kursus di antara 100,000 kursus membutuhkan lebih dari 5,000 putaran: sekitar 5 × 10^8 pemeriksaan.
Algoritma
- Tandai setiap mata kuliah sebagai belum diambil.
- Tandai suatu mata kuliah sebagai terhalang jika ada pasangan yang menetapkan prasyarat untuknya yang belum diambil.
- Ambil setiap mata kuliah yang belum diambil dan tidak terhalang.
- Jika tidak ada mata kuliah yang diambil pada putaran ini, berhenti; jika tidak, kembali ke langkah 2.
- Kembalikan true jika setiap mata kuliah sudah diambil.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCoursesPencarian mendalam terlebih dahulu dengan tiga status
Intuisi
Depth first search menemukan siklus dengan melacak jalur yang sedang dilaluinya. Beri setiap mata kuliah salah satu dari tiga status: belum dikunjungi, berada di jalur, selesai. Ikuti panah dari suatu mata kuliah ke mata kuliah yang menunggunya. Tandai mata kuliah sebagai berada di jalur saat kamu memasuki mata kuliah itu, dan selesai saat semua panahnya sudah ditelusuri.
Panah menuju mata kuliah yang berada di jalur menutup sebuah perulangan: kembalikan false. Panah menuju mata kuliah yang selesai aman, karena semua yang dapat dicapai darinya sudah diperiksa dan tidak memiliki siklus, jadi mata kuliah yang dicapai dua kali belum tentu merupakan siklus. Setiap mata kuliah dimasuki satu kali dan setiap panah diikuti satu kali: O(V + E).
Algoritma
- Bangun daftar kursus yang menunggu setiap kursus.
- Untuk setiap kursus yang belum dikunjungi, tandai kursus itu di jalur dan masukkan ke stack.
- Lihat bagian teratas stack. Jika tidak ada panah tersisa, tandai kursus itu selesai dan keluarkan dari stack; jika tidak, ikuti panah berikutnya.
- Jika panah mengarah ke kursus yang ada di jalur, return false. Jika panah mengarah ke kursus yang belum dikunjungi, tandai kursus itu di jalur dan masukkan ke stack.
- Jika semua kursus sudah selesai, return true.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return TrueAlgoritma Kahn
Intuisi
Sebuah pelajaran menjadi bebas pada satu saat: ketika prasyarat terakhirnya diambil. Jadi, simpan derajat masuk setiap pelajaran, yaitu jumlah prasyarat yang masih harus dipenuhi, lalu mulai antrean dengan setiap pelajaran yang jumlahnya 0. Mengambil sebuah pelajaran mengurangi jumlah setiap pelajaran yang menunggunya, dan pelajaran dengan jumlah yang mencapai 0 masuk ke antrean. Dalam contoh pertama, jumlahnya dimulai dari 0, 1, 1, 1: mengambil 0 membebaskan 1, lalu mengambil 1 membebaskan 2 dan 3. Setiap pelajaran masuk ke antrean satu kali dan setiap pasangan mengurangi satu jumlah satu kali: O(V + E).
Jika antrean kosong sementara pelajaran a belum diambil, jumlahnya lebih dari 0, jadi ada prasyarat a yang juga belum diambil, dan seterusnya. Penelusuran itu pasti akan mengunjungi kembali sebuah pelajaran: sebuah siklus. Sebaliknya, setiap pelajaran dalam sebuah siklus menunggu pelajaran lain di dalam siklus itu, jadi tidak ada yang bisa diambil lebih dulu. Urutan pelajaran keluar dari antrean merupakan jadwal yang valid.
Algoritma
- Untuk setiap pasangan [a, b], tambahkan a ke daftar kursus yang menunggu b, dan tambahkan 1 ke derajat masuk a.
- Masukkan setiap kursus dengan derajat masuk 0 ke dalam antrean.
- Ambil satu kursus dari antrean dan hitung. Kurangi derajat masuk setiap kursus yang menunggu kursus tersebut, lalu masukkan setiap kursus yang derajat masuknya menjadi 0 ke dalam antrean.
- Saat antrean kosong, kembalikan apakah jumlahnya sama dengan
numCourses.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
Jebakan dan kasus tepi
- Keliru memahami arah.
[a, b]berarti b datang lebih dulu: panah mengarah dari b ke a, dan derajat masuk a bertambah. - Lupa memasukkan kursus yang tidak muncul dalam pasangan mana pun. Dengan
numCourses = 5dan satu-satunya pasangan[4, 3], kursus 0, 1, dan 2 juga harus masuk ke antrean sejak awal. - Menggunakan dua status alih-alih tiga dalam penelusuran depth first search. Pada bentuk wajik 0 → 1, 0 → 2, 1 → 3, 2 → 3, kursus 3 dicapai dua kali dan tampak seperti siklus jika kamu hanya melacak "seen".
- Melakukan rekursi pada rantai yang terdiri dari 5.000 kursus: kedalaman 5.000 pemanggilan, melewati batas default Python sebesar 1.000.
- Mengembalikan true saat antrean kosong tanpa memeriksa apakah
numCourseskursus telah diambil. Contoh kedua akan mengembalikan true.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu dari masalah Course Schedule?
O(V + E), dengan V sebagai jumlah kursus dan E sebagai jumlah pasangan, menggunakan algoritma Kahn atau pencarian depth first. Setiap pasangan dibaca satu kali, dan setiap kursus ditangani satu kali. List dan jumlahnya membutuhkan ruang O(V + E).
Haruskah kamu menggunakan BFS atau DFS untuk Penjadwalan Kursus?
Keduanya berjalan dalam O(V + E). Algoritma Kahn, versi pencarian melebar, tidak perlu mengkhawatirkan kedalaman rekursi dan memberimu urutan kursus yang valid. Pencarian mendalam dengan tiga status adalah pilihan yang tepat ketika kamu juga harus melaporkan siklusnya, karena kursus-kursus di dalam tumpukannya membentuk siklus tersebut.
Apa itu pengurutan topologis?
Urutan simpul dalam graf berarah yang membuat setiap panah mengarah ke depan; dalam konteks ini, urutan yang menempatkan setiap prasyarat sebelum kursus yang membutuhkannya. Urutan ini ada tepat ketika graf tidak memiliki siklus, dan urutan kursus yang dihasilkan oleh algoritma Kahn adalah salah satunya. Course Schedule menanyakan apakah urutan seperti itu ada.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def canFinish(numCourses, prerequisites):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Output yang diharapkan
true