解説
(この 問題A は、ABC404-C と同じです。)
まず、グラフがサイクルグラフになるための必要十分条件は以下の条件を両方満たすことです。
- 全ての頂点の次数が
- グラフが連結である。
これを踏まえてmoguさんの判定方法を見てみると、
- 任意の頂点について、その頂点から同じ辺を 回使うことなく頂点間を移動して帰ってこれるような経路が存在する。
という条件が グラフが連結である の代わりに書かれています。この2つの条件は同値でしょうか?
答えはNoです。たとえば以下のような反例が考えられます。(ABC404-C の想定誤解法1の反例)
6 6 1 2 2 3 3 1 4 5 5 6 6 4
反例のように、独立した複数のサイクルをもつようなグラフは 全ての頂点の次数が 2 であり、 任意の頂点について、その頂点から同じ辺を2回使うことなく頂点間を移動して帰ってこれるような経路が存在する が 連結ではない グラフとなっています。
よって、moguさんの判定方法ではサイクルグラフであると判定されますが、実際にはサイクルグラフになりません。このようなテストケースを出力することでmoguさんのコードを撃墜できます。