与えられたグラフがサイクルグラフであることの必要十分条件は次の2つをともに満たすことです

• 全ての頂点の次数が \(2\) である
• 連結である

これはDFS/BFS/Union-Findなどを用いることで判定することができます。

Union-Findの練習問題：ALPC A
（この練習問題は連結性を動的に管理する問題であるため、DFS/BFSでは解けません）

想定誤解法1

• 全ての頂点の次数が \(2\) である

反例

6 6
1 2
2 3
3 1
4 5
5 6
6 4

想定誤解法2

• 連結である
• \(N=M\) である

反例

4 4
1 2
2 3
3 1
1 4