トポロジカルソート
有向グラフで頂点数が
v、辺が e 本あるとき、頂点を特定の順序で並べたいと考えます。もし v1 から v2 へ辺があるなら、その辺の始点である頂点 v1 は、頂点リストの中で v2 よりも先に現れなければなりません。つまり、並び替えた結果、各辺は小さいインデックスから大きいインデックスに向かって伸びるようになります。🤔
有効なトポロジカルソートは複数存在する場合があります。
一方、グラフにサイクルが含まれていると、トポロジカルソートはできません。
このアルゴリズムは、まだ訪問していない頂点から順に深さ優先探索（DFS）を行うことで実装できます。それぞれの DFS では、まず現在の頂点から到達できる子頂点を再帰的に処理し、それらをすべて処理し終わってから、現在の頂点を結果リストに追加します。こうすることで、ある頂点から到達できる頂点は、常にその頂点より前に処理される（つまり、元の頂点は“遅れて”追加される）ことが保証されます。アルゴリズムの最後に、結果リストを逆順に並べ替えれば、求めるトポロジカルオーダーが得られます。
used = [False] * n # 使用済みの頂点を管理
order = [] # トポロジカル順序
def dfs(v): # dfs
used[v] = True # 頂点 v を訪問済みにする
for to in g[v]: # v から到達できる各頂点 to に対して
if not used[to]: # 訪問していないなら
dfs(to) # 再帰的に dfs を呼び出す
order.append(v) # v をトポロジカル順序リストに追加
for i in range(n): # すべての頂点について
if not used[i]: # 訪問していない頂点があれば
dfs(i) # その頂点から dfs を開始
print(*order[::-1]) # トポロジカルオーダーを出力チャレンジ: コーススケジュールを組み立てる
あなたが履修したいコースは
n 個あり、それぞれのコースには合計で p 個の事前履修条件があります。各条件は のペアで表され、これは「コース を履修する前にコース を先に取らなければならない」ことを意味します。（たとえば、(1, 2) というペアなら、コース 1 を取るより先にコース 2 を修了しなければならないということです。）すべてのコースを修了できるかどうかを判定してください。
入力
最初の行には、整数
n と p が空白区切りで与えられます (1 ≤ n, p ≤ 10 000)。続く
p 行では、それぞれ のペアが与えられます (1 ≤ ≤ n)。出力
もしすべてのコースを修了できるなら
Yes、できない場合は No を出力してください。例
入力 | 出力 |
2 1
2 1 | Yes |
2 2
2 1
1 2 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB