問題は「与えられるグラフは一筆書きできるか」と言い換えることができます。 連結なグラフが一筆書きできるかを判定するには、以下のよく知られた条件を用いればよいです。
連結なグラフは以下のいずれかの条件に当てはまれば、一筆書きできる。 ・すべての頂点の次数が偶数 ・次数が奇数であるものがちょうど 2 つ
実装は、全ての頂点についてその次数が奇数であるものをカウントし、カウントが または であれば Yes
、そうでなければ No
を出力します。
入力はグラフの表現方法の一つである隣接リスト形式の受け取り方をしても良いですが、
今回は頂点から辺が何本出ているかを数えれば良いだけなので、以下のような実装で事足ります。