トポロジカルソート可能かを判定 (paizaランク A 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

有向グラフ G について、下図の通り、全ての辺が同じ方向になるように頂点を一列に並べることを「トポロジカルソート」といいます。

・有向グラフ G

・トポロジカルソート後の G

トポロジカルソートは全ての有向グラフについて可能という訳ではありません。例として下図のようなグラフでは頂点をどのように並べても逆向きの辺が現れてしまいます。

グラフの頂点・辺についての情報が与えられるので、このグラフがトポロジカルソート可能であるかを出力してください。
なお、このグラフには、多重辺や自己ループはないものとします。

・ヒント
入力されるグラフがトポロジカルソートが可能だと仮定して考えてみましょう。
トポロジカルソートが可能な場合、「入次数が 0 の頂点と、その頂点と繋がっている辺を削除する」操作を繰り返すことで全ての頂点を削除することができます。
このことを実際に試してみることでトポロジカルソート可能かを判定することができます。

例としてトポロジカルソート後の G に対してこの処理をおこなうと次のとおりになります。

入力される値

N M        
a_1 b_1         
...         
a_M b_M

・ 1 行目には、頂点の数 N と、辺の数 M が与えられます。
・続く M 行では、各辺の始点 a_i と、終点 b_i が与えられます。(1 ≦ i ≦ M)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 与えられたグラフがトポロジカルソート可能である場合は "Yes" を、そうでない場合は "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 3
2 4

出力例1: Yes

入力例2: 5 9
1 3
2 4
2 5
5 1
2 1
1 2
3 4
3 5
1 5

出力例2: No

問題一覧へ戻る