最大流問題 6 Perl編（paizaランク A 相当）

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

問題

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

n 頂点 m 辺の無向グラフが与えられます。各頂点には 1 から n までの番号がついており、各辺は頂点 a_i と頂点 b_i を結んでいます。(1 ≦ i ≦ m)
このグラフ上で、paiza 君は頂点 s から頂点 t へ、izapa 君は頂点 t から頂点 s へ向かおうと思っています。
2 人は途中で鉢合わせたくないので、全体を通して同じ辺を絶対に通らないようにしたいと思っています。
そのようなことが可能か、つまり、同じ辺を使用しない 2 つのパス (s から t へのパスと t から s へのパス) の組が存在するか判定してください。

入力される値

n m s t
a_1 b_1
a_2 b_2
...
a_m b_m

・ 1 行目に、グラフの頂点数を表す整数 n, グラフの辺数を表す整数 m, 2 頂点の番号を表す整数 s, t が半角スペース区切りで与えられます。
・続く m 行では、各辺の情報を表す整数 a_i, b_i が半角スペース区切りで与えられます。(1 ≦ i ≦ m) a_i, b_i は、辺の端点の頂点の番号を表します。

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

期待する出力: 2 人が同じ辺を使用しないで移動することが可能ならば 'Yes' を、そうでないならば 'No' を出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。

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

・入力はすべて整数
・ 2 ≦ n ≦ 100 = 10^2
・ 1 ≦ m ≦ 10,000 = 10^4
・ 1 ≦ s, t, a_i, b_i ≦ n
・ s ≠ t, a_i ≠ b_i
・ (a_i, b_i) ≠ (a_j, b_j) (i ≠ j)

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

出力例1: Yes

問題一覧へ戻る