グラフが二部グラフかどうかを判定
あるグラフが、隣接するどの頂点同士も同じ色にならないように、2色で彩色できる場合、そのグラフは二部グラフ（二分グラフ）と呼ばれます。
グラフが二部グラフであるかどうかを判定すると、スケジューリングやリソース割り当て、衝突回避といった分野で有効な構造や性質を把握できます。また、二部グラフを活用すれば、最大マッチングやグラフ彩色などのアルゴリズムを簡略化でき、より効率的な最適化が可能です。
あなたには
v 個の頂点と e 個の辺をもつ無向グラフが与えられます。このグラフが二部グラフかどうかをチェックしてください。入力
最初の行には、整数
v (1 ≤ v ≤ 100 000) と e (1 ≤ e ≤ 100 000) が与えられます。続く
e 行には、それぞれ v1 と v2 (1 ≤ v1, v2 ≤ v) のペアが記載されます。これは頂点 v1 と頂点 v2 が互いに接続していることを表します。出力
もし与えられたグラフが二部グラフであれば
Yes、そうでなければ No を出力してください。例
Input | Output |
2 1
2 1 | Yes |
3 2
2 1
1 3 | Yes |
3 3
1 2
1 3
2 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB