Module: トポロジカルソート


Problem

1 /5


トポロジカルソート

Theory Click to read/hide

アルゴリズムは次のように説明できます:
n 個の頂点と m 個のエッジを持つ有向グラフが与えられます。各エッジが小さい番号の頂点から大きい番号の頂点につながるように、頂点の番号を付け直す必要があります。
言い換えれば、グラフのすべての辺によって与えられる順序に対応する頂点の順列 (トポロジカル順序) を見つける必要があります。
深さ優先検索 (dfs(v)) を使用します
\(dfs(v)\)  から終了するときにリストの先頭に頂点を追加すると、最後にこのリストでは、トポロジカルなソートが得られます。
したがって、目的のトポロジー ソート —これは退出時間の降順で並べ替えられています。

Problem

重み付けされていない有向グラフが与えられた場合。 トポロジー的に並べ替える必要があります。

入力: 最初の行には 2 つの自然数 n と m (1≤n≤105, 1≤m≤10< sup >5) —それぞれグラフの頂点と辺の数。次の m 行には、グラフのエッジがリストされています。各エッジは、数値のペアで指定されます —それぞれ開始頂点と終了頂点の番号。
 
出力: グラフのトポロジカル ソートを一連の頂点番号として出力します。グラフをトポロジー的にソートできない場合は、−1.
を出力してください。 最初の行には、頂点 N とエッジ M の数が含まれています。 

<頭> <本体>
# 入力 出力
1 4 4
14
4 3
4 2
3 2
1 4 3 2