1. paizaラーニングトップ
  2. レベルアップ問題集
  3. グラフ構造の入力メニュー(言語選択)
  4. 問題一覧
  5. オイラーグラフ・有向グラフ

グラフ構造の入力メニューのサムネイル
オイラーグラフ・有向グラフ(paizaランク B 相当)

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

問題

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

いくつかの頂点と、それらのうち 2 つの頂点を結ぶ辺の集合をグラフといいます。特に、辺に向きがつけられている場合は有向グラフといいます。

さらに、有向グラフを無向グラフとしてみたときに、どの 2 つの頂点間も辺をたどって行き来ができるような場合は、弱連結なグラフといいます。下の図は、頂点の数が 5 の弱連結な有向グラフの一例です。



1, ..., n の番号がついた n 個の頂点と、1, ..., m の番号がついた m 個の辺からなる弱連結な有向グラフを考えます。

整数 n, m と、m 個の頂点の組 (a_1, b_1), ..., (a_m, b_m) が与えられます。

頂点の組 (a_i, b_i) は、頂点 a_i から 頂点 b_i に向かって辺が伸びていることを表します。

そして、これら以外に辺はありません。

このとき、以下の条件を用いて、このグラフにおいて、ある頂点から始めてすべての辺を一筆書きして最初の頂点に戻ってくることができるかどうか判定してください。なお、そのようなことが可能なグラフをオイラーグラフといいます。


弱連結な有向グラフにおいて、ある頂点から始めてすべての辺を一筆書きして最初の頂点に戻ってくることができるための必要十分条件は以下のようになります。

・すべての頂点において、入次数と出次数が一致する。



ただし、ここでいう入出次数とは、以下の形式で表現されるものとします。


頂点 i に向かっている辺の個数を頂点 i の入次数といいます。
頂点 i から出ている辺の個数を頂点 i の出次数といいます。

下の図は、ある有向グラフの頂点の入次数を左側の整数、出次数を右側の整数で表したものです。

入力される値

n m
a_1 b_1
...
a_m b_m

・ 1 行目に、頂点の個数を表す整数 n と、頂点の組の個数を表す整数 m が半角スペース区切りで与えられます。
・ 続く m 行では、頂点の組 a_i, b_i が半角スペース区切りで与えられます。(1 ≦ i ≦ m)


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

与えられたグラフにおいて、ある頂点から始めてすべての辺を一筆書きして最初の頂点に戻ってくることができる場合は 1, そうでない場合は 0 を出力してください。

また、末尾に改行を入れ、余計な文字を含んではいけません。

条件

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

・ 入力はすべて整数
・ 2 ≦ n ≦ 100
・ n - 1 ≦ m ≦ 10000 = 10^4
・ 1 ≦ a_i, b_i ≦ n
・ 与えられるグラフは弱連結である

入力例1

3 2
1 2
2 3

出力例1

0

入力例2

3 4
1 2
2 1
2 3
3 2

出力例2

1

問題一覧へ戻る

ページの先頭へ戻る