トポロジカルソート（幅優先探索） C編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
有向グラフ G について、下図の通り、全ての辺が同じ方向になるように頂点を一列に並べることを「トポロジカルソート」といいます。
今回は幅優先探索を用いてトポロジカルソートを実装してみましょう。
入力されるグラフがトポロジカルソートが可能だと仮定して考えてみましょう。
トポロジカルソートが可能であるための必要十分条件は、「【入次数が 0 の頂点とその頂点から伸びている辺を削除する操作】を繰り返すことで全ての頂点を削除することができる」です。
このことを実際に試してみることでトポロジカルソート可能かを判定することができます。
この手順で頂点を削除していった順番がそのままトポロジカルソートされた頂点の順番となります。
グラフの頂点・辺についての情報が与えられるので、このグラフがトポロジカルソート可能であるかを判定し、トポロジカルソートが可能である場合はトポロジカルソートをした後の頂点番号を順に出力してください。
なお、このグラフには、多重辺や自己ループはないものとし、頂点の出力は「辺の向きが最初に出力した頂点から最後に出力した頂点に向かうように」出力するものとします。
なお、トポロジカルソートした結果が複数存在する場合はそれらのうち 1 つを出力してください。
- 入力される値
-
N M
a_1 b_1
...
a_M b_M
・ 1 行目には、頂点の数 N と、辺の数 M が与えられます。
・ 続く M 行では、各辺の始点 a_i と、終点 b_i が与えられます。(1 ≦ i ≦ M)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
与えられたグラフがトポロジカルソート可能である場合は、「辺の向きが最初に出力した頂点から最後に出力した頂点に向かうように」各頂点を改行区切りで出力してください。トポロジカルソートが不可能である場合は "No" を出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 200
・ 1 ≦ M ≦ N × (N - 1) / 2
・ 1 ≦ a_i,b_i ≦ N
- 入力例1
-
4 5
1 2
2 3
3 4
1 4
2 3
- 出力例1
-
1
2
3
4
- 入力例2
-
5 7
1 2
2 3
3 4
1 4
2 3
2 5
5 2
- 出力例2
-
No
