二部グラフ判定（paizaランク A 相当）

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

問題

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

多重辺・自己ループのない無向グラフを構成する 1 〜 N の番号がつけられた頂点とそれらを結ぶ M 本の辺の情報が与えられるので、このグラフが二部グラフかを判定してください。

・二部グラフとは
グラフの全ての頂点を 2 つの頂点集合に分割して、各集合間の頂点を互いに隣接しないようにできるグラフのことです。
言い換えると、グラフの頂点を 2 色で塗り分けたとき、全ての辺の両端の色が異なるような塗り方が存在するとき、そのグラフは二部グラフといえます。
例として、上のグラフは全ての辺の両端の頂点の色が異なるように 2 色で塗り分けられるため二部グラフであり、下のグラフはそのような塗り分けが存在しないため、二部グラフではありません。

入力される値

N M
a_1 b_1
...
a_M b_M

・ 1 行目では、頂点の数 N と辺の本数 M が半角スペース区切りで与えられます。
・続く M 行では、M 個の辺の両端の頂点の番号 a_i, b_i (1 ≦ i ≦ M) が与えられます。

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

期待する出力: 与えられたグラフが二部グラフである場合は "Yes" を、そうでない場合には "No" を出力してください。

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

・1 ≦ N ≦ 5,000
・1 ≦ M ≦ min(N*(N-1)/2, 100,000)
・1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ M)
・a_i ≠ b_i (1 ≦ i ≦ M)

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

出力例1: Yes

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

出力例2: No

問題一覧へ戻る