弱連結性の判定 Ruby編（paizaランク A 相当）

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

問題

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

1,...,N の番号のついた N 個の頂点とそれらをつなぐ枝からなる有向グラフを考えます。ただし、自己ループと多重辺は考えません。

M 本の有向枝が与えられます。この M 本の有向枝からなる有向グラフが弱連結ならば Yes そうでなければ No と出力してください。

ただし、有向グラフ G が弱連結であるとは、G の有向枝をすべて無向枝に置き換えた無向グラフ G' が連結である（グラフの任意の頂点対に経路が存在する）ということです。

入力される値

N M
a_1 b_1
...
a_M b_M

1 行目に、頂点の個数を表す整数 N と、枝の本数を表す整数 M が与えられます。

i + 1 行目に枝 i を表す整数の組 (a_i,b_i) が与えられます。枝 i は、頂点 a_i から頂点 b_i に向かう枝です。(1 ≦ i ≦ M)

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

期待する出力: 1 行で出力してください。与えられたグラフが弱連結ならば Yes、そうでなければ No と出力してください。

また末尾に改行をいれ、余計な文字、空行を含んではいけません。

条件

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

入力はすべて整数

2 ≦ N ≦ 100

1 ≦ M ≦ N × (N-1)

1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ M)

a_i ≠ b_i (1 ≦ i ≦ M)

同じ頂点の組（順序組）は 2 回以上入力されない

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

出力例1: Yes

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

出力例2: No

問題一覧へ戻る