Course Schedule
numCourses 個のコースがあり、番号は 0 から numCourses-1 までです。prerequisites 内の各ペア [a, b] は、コース a を始める前にコース b を修了する必要があることを意味します。すべてのコースを修了できる順序が存在する場合は true を、存在しない場合は false を返してください。
関数
- numCoursesinteger
- コースの数
- prerequisitesinteger-2d-array
- ペア [a, b] は、それぞれコース b がコース a より先に履修されることを意味します
- 戻り値boolean
- すべてのコースを修了できる場合は true、そうでない場合は false
制約
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- 各ペア
[a, b]について、0 ≤ a, b < numCoursesです。 - 同じペアは2回現れません。
- 1組のペアで、同じコースを2回指定することがあります。
[a, a]。そのコースは自分自身を先に受講する必要があるため、受講することはできません。
例
- 入力
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- 出力
- true
- 説明
- コース0には前提条件がないため、まず履修します。これによりコース1を履修できるようになり、さらに2と3も履修できるようになるので、0、1、2、3の順序で問題ありません。
- 入力
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- 出力
- false
- 説明
- コース0は2を待ち、2は1を待ち、1は0を待ちます。この3つはループ状に互いを待っているため、どれも先に進むことができません。
発展問題
各科目の前提科目をそれ以前の学期に修了していれば、1学期にいくつでも科目を履修できます。すべての科目を履修するのに必要な学期数の最小はいくつですか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各コースを点として、各ペア
[a, b]をbからaへの矢印として描きます。その図にどのような形があると、最後まで終えられなくなりますか？矢印がループしています。ループ内のすべてのコースが、同じループ内の別のコースを待っているため、どのコースも先に進むことができません。問題は、グラフにサイクルがあるかどうかです。
各コースがまだいくつの前提科目を待っているか数えます。カウントが0のコースをキューに入れ、そのコースを1つ取り出すたびに、それを待っているすべてのコースのカウントを減らします。キューに入るコースが
numCoursesより少なければ、循環があります。
解説
各ペア [a, b] について、矢印 b → a を描きます。頂点 V = numCourses 個、矢印 E = prerequisites.length 本のこのグラフにサイクルがない場合に限り、すべてのコースを修了できます。Kahnのアルゴリズムは、学生が学習計画を立てるようにこれを確認します。前提条件を終えたコースを順に受講し、すべてのコースを受講できるかを調べます。
すべての無料コースを、何度でも受講しよう
正しいが、最大のテストでは終わらない
考え方
各ラウンドで、前提条件がすべて満たされている未受講のコースをすべて受講済みにします。あるラウンドで受講済みになるコースがなければ停止し、すべてのコースが受講済みなら true と答えます。受講済みになるコースがないのは、残っているすべてのコースが別の未受講コースを待っている場合だけで、これは循環です。
各ラウンドで、すべてのペアとすべてのコースを読み直しますが、受講済みになるコースは1つだけの場合もあります。100,000コースの中に5,001コースの連鎖があると、5,000回を超えるラウンドが必要です。チェック回数は約5 × 10^8回になります。
アルゴリズム
- すべてのコースを未履修としてマークします。
- 未履修の前提条件がある組が存在する場合、そのコースを履修不可としてマークします。
- 履修済みでも履修不可でもないすべてのコースを履修します。
- このラウンドで何も履修しなかった場合は終了します。そうでなければ、ステップ 2 に戻ります。
- すべてのコースが履修済みなら true を返します。
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 == numCourses3つの状態を使った深さ優先探索
考え方
深さ優先探索では、たどっている経路を追跡してサイクルを見つけます。各コースに「未訪問」「経路上」「完了」の3つの状態を割り当てます。あるコースから、そのコースを待っているコースへ矢印をたどります。コースに入ったときに「経路上」と印を付け、すべての矢印を調べ終えたら「完了」と印を付けます。
経路上のコースに向かう矢印があれば、ループが閉じます。return false とします。完了したコースに向かう矢印は安全です。そのコースから到達できるものはすべて調べられており、サイクルがないことが確認済みだからです。そのため、コースに2回到達しただけではサイクルとは限りません。各コースに入るのは1回、各矢印をたどるのも1回です。計算量は O(V + E) です。
アルゴリズム
- 各コースについて、そのコースを待っているコースのリストを作成します。
- 未訪問の各コースについて、経路上にあるとマークし、スタックにプッシュします。
- スタックの一番上を確認します。残っている矢印がなければ、完了とマークしてポップします。そうでなければ、次の矢印をたどります。
- 矢印の先が経路上のコースなら、false を返します。未訪問のコースなら、そのコースを経路上にあるとマークし、スタックにプッシュします。
- すべてのコースが完了したら、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 Trueカーンのアルゴリズム
考え方
コースは、最後の前提コースを履修した時点で履修可能になります。そこで各コースの入次数、つまり、まだ履修を待っている前提コースの数を記録し、数が 0 のコースすべてをキューに入れて開始します。あるコースを履修すると、そのコースを待っている各コースの数が減り、数が 0 になったコースはキューに入ります。最初の例では、数は 0、1、1、1 から始まります。0 を履修すると 1 が履修可能になり、1 を履修すると 2 と 3 が履修可能になります。各コースはキューに 1 回だけ入り、各組について数を減らす処理も 1 回だけ行います：O(V + E)。
コース a が未履修のままキューが空になった場合、a の数は 0 より大きいため、a の前提コースも未履修であり、同様に続いていきます。このたどり方では、必ず同じコースに再び到達します。つまり、サイクルです。逆に、サイクル上の各コースは、そのサイクル上の別のコースを待っているため、どのコースも最初には履修できません。コースがキューから取り出される順序が、有効な履修順序です。
アルゴリズム
- 各ペア [a, b] について、bを待つコースのリストにaを追加し、aの入次数に1を加えます。
- 入次数が0のすべてのコースをキューに入れます。
- キューからコースを1つ取り出してカウントします。そのコースを待っているすべてのコースの入次数を減らし、入次数が0になったコースをそれぞれキューに追加します。
- キューが空になったら、カウントが
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
落とし穴と境界ケース
- 方向を取り違えること。
[a, b]はbが先に来ることを意味します。矢印はbからaに向かい、aの入次数が増えます。 - どのペアにも現れないコースを忘れること。
numCourses = 5で、ペアが[4, 3]だけの場合、コース0、1、2もキューに入れて開始する必要があります。 - 深さ優先探索で状態を3つではなく2つにすること。ひし形の形で0 → 1、0 → 2、1 → 3、2 → 3とつながっている場合、コース3には2回到達するため、「訪問済み」だけを記録していると、サイクルのように見えてしまいます。
- 5,000コースの連鎖を再帰で処理すること。再帰呼び出しが5,000段になり、Pythonのデフォルト上限である1,000を超えてしまいます。
numCourses個のコースを履修したか確認せずに、キューが空になった時点でtrueを返すこと。2つ目の例ではtrueが返されてしまいます。
よくある質問3
Course Schedule 問題の時間計算量はどれくらいですか？
O(V + E)。ここで、V はコース数、E はペア数です。Kahn のアルゴリズムまたは深さ優先探索を使います。各ペアは一度ずつ読み取られ、各コースは一度ずつ処理されます。リストとカウントに O(V + E) の領域を使用します。
コーススケジュールには BFS と DFS のどちらを使うべきですか？
どちらも O(V + E) で実行されます。幅優先探索版のKahnのアルゴリズムは、再帰の深さを気にする必要がなく、有効なコースの順序を求められます。サイクルも報告する必要がある場合は、3つの状態を使う深さ優先探索が自然な選択です。スタック上のコースがサイクルを構成するためです。
トポロジカルソートとは何ですか？
有向グラフのノードを並べる順序で、すべての矢印が前向きになるものです。ここでは、すべての前提科目が、それを必要とする科目より先に来る順序を指します。グラフにサイクルがない場合に限り、この順序が存在します。Kahn's algorithm が科目を取り出す順序もその一例です。Course Schedule では、このような順序が存在するかどうかを問います。
def canFinish(numCourses, prerequisites):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
期待される出力
true