有向グラフの閉路検出 Go編（paizaランク A 相当）

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

問題

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

有向グラフ G についての情報が与えられるので、G に閉路が存在する場合は "Yes" を、存在しない場合は "No" を出力してください。

なお、G に閉路が存在するとは、有向辺(V_i, V_{i+1}) (1 ≦ i ≦ n-1) と (V_n, V_1) が存在する 2 頂点以上の頂点列 (V_1, ..., V_n) を G の頂点から取り出すことができることを指します。

例として上のグラフが与えられた場合は閉路が含まれないため No を出力してください。また、下のグラフが入力として与えられた場合は 6->5->4->6 という閉路が含まれるため Yes を出力してください。

入力される値

N M
a_1 b_1
...
a_M b_M

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

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

期待する出力: G に閉路が存在する場合は "Yes" を、存在しない場合は "No" を 1 行で出力してください。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ N ≦ 200
・ 1 ≦ M ≦ N × (N - 1) / 2
・ 1 ≦ a_i,b_i ≦ N

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

出力例1: No

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

出力例2: Yes

問題一覧へ戻る