047 Bipartite Graphの問題について

[yaneurao]

この問題、二部グラフであるかを判定させる問題なのですが、テストケースに非連結なグラフがテストケースにあって嫌らしいです。二部グラフの常識なのかも知れませんが、書籍のほうでその説明がなく、問題のほうにもその説明がないまま非連結なグラフを与えて、テストケースにだけ忍ばせてあるのはちょっと嫌らしい感じはします。

本問の入力例1を見ると、よく見ると非連結なグラフなのですが(それに気づかない人が大半だと思う)、運悪くこれは出力例がYesになっているケースになっています。なので、DFSで頂点1からカラーリングしていき、矛盾が生じないかチェックするような場合、矛盾は生じないのでYes判定となってしまい、このテストケースには引っかからないのです。せめてこのテストケースがNoであるようなものであり、コメントに「非連結なグラフが与えられる場合があります」とでも書いてあれば良かったのですが…。