Course Schedule IとII
履修条件を有向グラフとしてモデル化し、トポロジカルソートを使ってすべての講座を修了できるかどうかと、その順序を求めます。
「Course Schedule IとII」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
問題の概要
Course Schedule I（LeetCode 207）では、n個のコースと、[a, b]という形式で「bをaより前に受講する必要がある」ことを表すprerequisitesのペアのリストが与えられ、すべてのコースを修了できるかを判定します。Course Schedule II（LeetCode 210）では、コースを受講する実際の順序を返し、不可能な場合は空の配列を返します。どちらも、前提条件をエッジとして表す有向グラフ上のトポロジカルソートに帰着できます。
グラフのモデル化
有向グラフを構築します。各前提条件のペア[a, b]に対して、b → aというエッジを追加します。「bをaより前に処理する必要がある」ため、bからaへつなげます。各コースの入次数を計算します。入次数が0のコースには前提条件がなく、すぐに受講できます。この問題が解けるのは、このグラフにサイクル（循環依存）が存在しない場合に限ります。
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))Course Schedule I：Kahn法による解法
Kahn法を使用します。処理したコース数がnと等しければ、すべてのコースを修了できます。そうでなければ、循環依存によって修了できません。
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]])) # FalseCourse Schedule II：順序を返す
Course Schedule Iと同様ですが、処理したコースの順序を集めます。すべてのコースが含まれていればその順序を返し、そうでなければ空のリストを返します。
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]]))DFSを使ったCourse Schedule
DFSによるサイクル検出を使う別の方法もあります。コースには3つの状態があります。未訪問 (0)、処理中 (1)、完了 (2)です。DFS中に処理中のコースへ到達した場合、サイクルが存在します。この方法はKahn法と機能的には同等ですが、再帰的なDFSを使用します。
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エッジの向きが重要な理由
よくある間違いは、エッジの向きを逆にすることです。前提条件が[a, b]で「bをaより前に処理する」という意味なら、a → bではなくb → aというエッジを追加します。エッジの向きは依存関係の流れを反映しなければなりません。つまり、矢印は最初に処理するものから、それに依存するものへ向けます。向きを間違えると、サイクル検出と順序が逆になり、複数の依存関係がある問題で誤った結果になります。
Course Schedule III：貪欲法による変形問題
Course Schedule III（LeetCode 630）は別の問題です。コースには所要時間と締切があり、受講するコース数を最大化します。これは最大ヒープを使った貪欲法で解きます。常に締切が最も遅いコースを先に選び、コースを追加して締切を超えた場合は、これまでに選んだコースの中で最も長いもののほうが長ければ、それを置き換えます。これはトポロジカルソートではなく貪欲法の問題であり、問題文を注意深く読むことの重要性を示しています。
孤立ノードの扱い
前提条件も依存先もないコースは孤立ノードです。入次数が0で、出ていくエッジもありません。Kahn法ではこれらを正しく処理できます。すぐにキューへ追加され、処理されます。prerequisitesのリストに登場しないコースも含め、0からn - 1までのすべてのノードの入次数を0で初期化してください。初期化しないと、それらのコースが処理対象から漏れてしまいます。
# 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.コースを並行して修了する時間
Parallel Courses IIでは、1学期に最大k個のコースを受講でき、前提条件を守らなければならない場合に、すべてのコースを受講するための最小学期数を求めます。これには、レベルごとに処理するKahn法と、k個を選択する制約に対するビットマスクDPが必要です。トポロジカルソートとビットマスクDPを組み合わせた、非常に難しい問題です。
面接でのコミュニケーション戦略
面接でCourse Schedule系の問題に直面したら、次の手順で進めます。(1) すぐにトポロジカルソート／サイクル検出問題だと識別します。(2) エッジがどちら向きに進むかを明確にして、グラフをモデル化します。(3) 簡潔さを重視するならKahn法（BFS）、慣れている方法を使うならDFSを選択します。(4) サイクルがある場合を明示的に処理します。(5) 時間計算量O(V+E)に言及します。この体系的なアプローチによって、問題を組織的に解決する能力を示せます。
包括的なテスト
さまざまな入力に対して両方の解法をテストし、正しさを検証します。Kahn法は複数の有効な順序を柔軟に扱えます。Course Schedule 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理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について理解度を確認します。
レッスンのまとめ
このレッスンでは、Course Schedule IとIIはいずれも、前提条件[ a, b ]に対してエッジb → aを使うトポロジカルソートで解けること、Course Schedule Iではlen(order) == nを確認するだけなのに対し、Course Schedule IIでは順序そのものを返すこと、そして3つの状態を使ったDFSベースのサイクル検出は、Kahn法によるBFSの有効な代替手段であることを学びました。次は、強連結成分を求めるKosaraju法を学びます。
よくある質問
「Course Schedule IとII」レッスンは無料ですか？
はい。「Course Schedule IとII」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「Course Schedule IとII」で何を学びますか？
履修条件を有向グラフとしてモデル化し、トポロジカルソートを使ってすべての講座を修了できるかどうかと、その順序を求めます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「Course Schedule IとII」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- Kahnのアルゴリズム：BFSトポロジカルソート
- DFSの後順によるトポロジカルソート
- Course Schedule IとII
- Kosarajuによる強連結成分