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回現れることはありません。
- ペアには、同じコースが2回指定されることがあります（
[a, a]）。そのコースを受講するには、先にそのコース自体を受講する必要があるため、決して受講できません。
例
- 入力
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- 出力
- true
- 説明
- コース 0 には前提条件がないので、最初に受講します。そうするとコース 1 を受講でき、コース 1 を受講すると 2 と 3 の両方を受講できるので、0、1、2、3 の順序で問題ありません。
- 入力
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- 出力
- false
- 説明
- コース0は2を待ち、コース2は1を待ち、コース1は0を待ちます。この3つはループ状に互いを待っているため、どれも最初に履修することはできません。
提出時に隠しテスト+20件
発展問題
各学期には、各コースの前提条件がそれより前の学期に修了していれば、何科目でも履修できます。すべてのコースを履修するのに必要な学期数の最小値はいくつですか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各コースを点として、各ペア
[a, b]をbからaへの矢印として描きます。その図で、修了を不可能にする形はどのようなものでしょうか？矢印がループになっています。ループ上のすべてのコースは、同じループ上の別のコースを待っているため、どのコースも先に進むことができません。問題は、グラフにサイクルがあるかどうかです。
各コースがまだいくつの前提科目を待っているかを数えます。カウントが0のコースをキューに入れ、1つ取り出すたびに、それを待っている各コースのカウントを減らします。キューに入るコースが最終的に
numCourses未満なら、サイクルがあります。
解説
このペアを、V = numCourses 個のノードと E = prerequisites.length 本の辺を持つ有向グラフに変換します。各ペア [a, b] につき、b → a の矢印を1本引きます。そのグラフにサイクルがなければ、すべてのコースを修了できます。Kahnのアルゴリズムでは、学生が計画を立てるように判定します。前提条件をすべて満たしたコースを受講し続け、コースがなくなるのと選択肢がなくなるののどちらが先かを確認します。
無料コースを何度でも受講しましょう
正しいが、最大のテストでは終わらない
考え方
学生が考えるように計画しましょう。各ラウンドで、まだ履修していないすべてのコースを確認します。そのコースの前提条件をすべて履修済みなら、そのコースを履修します。何も履修できないラウンドが来るまで繰り返します。その時点ですべてのコースを履修済みなら、答えは真です。
進展のないラウンドが偽を意味する理由：そのラウンドで何も履修できなかった場合、残っている各コースには、まだ残っている前提条件があります。残っているコースのどれかから始め、まだ履修していない前提条件の1つへ進むことを繰り返します。進む先がなくなることはありません。コース数には限りがあるので、すでに訪れたコースに戻ってきます。これは循環であり、その中のコースは互いを待ち続け、いつまでも履修できません。
この方法は正しいですが、各ラウンドですべての組み合わせとすべてのコースを読み直し、1ラウンドで履修できるコースは最少で1つです。各コースが1つ前のコースを必要とする5,001コースの連鎖では、5,000ラウンドを超えることになります。100,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つの状態を割り当てます。
あるコースから、そのコースを待っているコースへ矢印をたどります。コースに入ったときに「経路上」とマークし、そのコースから出るすべての矢印を調べて戻るときに「完了」とマークします。経路上のコースを指す矢印があれば、円を描くようにたどったことになるため、false を返します。完了したコースを指す矢印は安全です。そのコースから到達できるものはすべて確認済みで、サイクルがないことが分かっているため、スキップします。各コースに入るのは1回だけで、各矢印をたどるのも1回だけです。
状態が2つだけでは不十分です。ダイヤモンド型の 0 → 1、0 → 2、1 → 3、2 → 3 では、探索は 2 を通って2回目にコース 3 に到達しますが、その時点で 3 は完了状態であり、経路上ではありません。サイクルもありません。ループを閉じるのは、現在の経路に戻る矢印だけです。
独自のスタックと、各コースについて次に調べる矢印の位置を使って探索を書きます。再帰版のほうが短くなりますが、コースが 5,000 個連なると、呼び出しの深さが 5,000 になります。
アルゴリズム
- 各コースについて、そのコースを待っているコースのリストを作成します。
- 未訪問の各コースを経路上としてマークし、スタックにプッシュします。
- スタックの一番上を確認します。残っている矢印がなければ、完了としてマークしてポップします。そうでなければ、次の矢印をたどります。
- 矢印の先が経路上のコースなら、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から3の数は最初、それぞれ0、1、1、1です。0を履修するとコース1の数が0になり、1を履修するとコース2と3の数が0になります。4つすべてを履修できるので、答えはtrueです。各コースがキューに入るのは最大1回で、各ペアが数を減らすのも1回だけなので、計算量はO(V + E)です。
未履修のコースが残るとサイクルがある理由：コースaが未履修のままキューが空になった場合、その数は0より大きいため、前提科目の1つであるbも未履修です。bについても同じことが成り立ちます。このように続けると、コースから未履修の前提科目へのたどり方は止まることがなく、いずれコースを再訪するため、サイクルになります。2つ目の例では、最初から数が0のコースがなく、キューは空のままで、3つのコースのどれも履修されません。
逆の方向も成り立ちます。サイクル上のコースは、同じサイクル上の別のコースを待っているため、そのコースが履修される前に数が0になることはなく、どのコースも最初に履修されることはありません。したがって、「すべてのコースを履修する」と「サイクルがない」は同じことを述べています。さらに、キューから取り出されたコースの順序は、有効な履修計画になります。
アルゴリズム
- 各ペア [a, b] について、bを待つコースのリストにaを追加し、aの入次数に1を加えます。
- 入次数が0のすべてのコースをキューに入れます。
- キューからコースを取り出して数えます。そのコースを待っているすべてのコースの入次数を減らし、入次数が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 は数に含まれます。ペアに登場したコースだけでなく、入次数が 0 のすべてのコースをキューに入れて開始します。 - 自分自身を前提条件とするコース、
[2, 2]。これは長さ 1 のサイクルです。入次数が 0 になることはなく、答えは false です。 - 深さ優先探索で状態を 3 つではなく 2 つだけ使う。ひし形の形の 0 → 1、0 → 2、1 → 3、2 → 3 では、コース 3 に 2 回到達します。「訪問済み」だけを記録していると、これはサイクルのように見えます。現在の経路に戻る矢印だけがループを作ります。
- 長い連鎖で再帰を使う。コースが 5,000 個の連鎖では、呼び出しの深さが 5,000 になり、Python のデフォルト上限である 1,000 を超えます。
- キューが空になったときに、履修したコース数を
numCoursesと比較せずに true を返す。
よくある質問4
Course Schedule問題の時間計算量はどれくらいですか？
O(V + E)。ここで、V はコース数、E はペアの数です。Kahn のアルゴリズムまたは深さ優先探索を使用します。リストの構築時に各ペアを一度ずつ読み取り、各コースがキューに入るのは最大 1 回で、各ペアによってカウントが 1 回減少します。リストとカウントに必要な空間は O(V + E) です。
カーンのアルゴリズムでコースが残ると、なぜサイクルがあることを意味するのでしょうか？
あるコースが残るのは、そのカウントが一度も0にならなかった場合に限られるため、その前提条件の少なくとも1つも残っています。コースからコースへと、その待ち状態をたどってみましょう。どの段階でも別の残ったコースにたどり着き、コースの数は有限なので、必ず一度訪れたコースに戻ってきます。2回訪れる間の経路がサイクルです。
Course Schedule には BFS と DFS のどちらを使うべきですか？
どちらも O(V + E) で実行されます。幅優先探索版であるカーンのアルゴリズムは、再帰の深さを心配する必要がなく、コースの有効な順序もそのまま得られます。3状態を使う深さ優先探索も同じ速さで、サイクルも報告する必要がある場合には自然な選択です。スタック上のコースがサイクルを構成するためです。
トポロジカルソートとは何ですか？
有向グラフのノードを並べた順序で、すべての矢印が前方を指すもの。この場合は、すべての前提条件が、それを必要とするコースより先に来るようにコースを並べた順序です。グラフにサイクルがない場合に限り存在し、カーンのアルゴリズムでコースを取り出す順序がその一例です。Course Scheduleでは、トポロジカル順序が存在するかどうかを問います。
Python
def canFinish(numCourses, prerequisites):
# ここにコードを書いてくださいケース1
ケース2
入力
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
期待値
true