#CP トポロジカルソート python

題名の通り、トポロジカルソートを実装してみようというものです。

トポロジカルソートとは…、

トポロジカルソート（英: topological sort）とは、グラフ理論において、有向非巡回グラフ（英: directed acyclic graph, DAG）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。
wikipedia:トポロジカルソート

アルゴリズムはwikiの疑似コードを読んでください。

入力されるグラフはDAGであると想定しておきます。
として、

• inpath[i] = ノードiに流れ込む辺の数
• outnode[i] = ノードiから流れ出る辺が向かうノードのリスト

とします。また、初期条件として

• S = 流れ込む辺の数が0であるようなノードの集合 = inpath[i] = 0となるようなiの集合
• L = 空リスト (ソート結果を保持するリスト)

としておきます。
するとpythonでのソースコードは以下となります。

n, m = map(int, input().split())
inpath = [0] * n
outnode = [[] for i in range(n)]
for i in range(m):
    x, y = map(lambda z:z-1,map(int, input().split())) # 添え字を1~nから0~n-1に調整
    outnode[x].append(y)
    inpath[y] += 1
S = []
L = []

for i in range(n):
    if inpath[i] == 0:
        S.append(i) #流入パスがないノードをSに追加

while S: # Sが空でない場合、続ける
    k = S.pop()
    L.append(k)
    for i in outnode[k]:
        inpath[i] -= 1
        if inpath[i] == 0:
            S.append(i)
            
print(L)

入力例

4 5
1 2
1 3
3 2
2 4
3 4

添え字は-1して調整してあります。

出力

[0, 2, 1, 3]