Path/Cycle - Topological Sort

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

トポロジカルソート


閉路のない有向グラフDAG は物事の手順を表すデータ構造として応用することができます。例えば、各仕事を頂点、仕事の順序を有向辺で表すことができます。上の図では、仕事 B に着手するためには、仕事A と仕事X の両方が完了している必要があります。このような関係を表すDAG に対して、トポロジカルソートを行うと、着手すべき順番に仕事を列挙することができます。DAG の各辺 $(u, v)$ について、$u$ が $v$ よりも先に位置するように並べることを、トポロジカルソートと言います。

与えられた DAG $G$ に対して、トポロジカルソートを行った頂点の並びを出力してください。

入力

入力は以下の形式で与えられます。

$|V|\;|E|$
$s_0 \; t_0$
$s_1 \; t_1$
:
$s_{|E|-1} \; t_{|E|-1}$

$|V|$, $|E|$ はそれぞれグラフ $G$ の頂点の数と辺の数を示します。グラフ $G$ の頂点はそれぞれ $0, 1, ..., |V|−1$ の番号が付けられているものとします。

$s_i$, $t_i$ はグラフ $G$ の $i$ 番目の有向辺が結ぶ2つの頂点の番号を表します。

出力

グラフ $G$ の頂点番号をトポロジカル順序で出力してください。各頂点の番号を1行に出力してください。

この問題では、1つの入力に対して複数の解答があります。条件を満たす出力は全て正解となります。

制約

  • $1 \leq |V| \leq 10,000$
  • $0 \leq |E| \leq 100,000$
  • グラフ $G$ はDAG である
  • グラフ $G$ に多重辺はない
  • グラフ $G$ に自己ループはない

入力例

6 6
0 1
1 2
3 1
3 4
4 5
5 2

出力例

0
3
1
4
5
2

Note

      解説