主要思路
这道题是要求你实现一个 Checker,来判断是否有长度相同的环。实现的主要方式是找出所有的环并放到桶里面进行统计。我们可以观察出一些简单的性质,来做一次判断:
- 如果存在一个边双连通分量,其 \(|E| – |V| \geq \sqrt{|V|} \),那么一定是存在两个同长环的。这个具体证明可以进行平方,然后发现差值的平方大于点数,感性理解:通过鸽巢定理,出会有一些边构造出相同长度的环。
之后,我们可以考虑把度数为 2 的点去掉,缩成一张新的图。然后,再做暴力的 DFS 来判断是否存在同长环:具体而言,选择一个起点,然后在 DFS 之后删去。
时间复杂度是 \(\Theta(n^2)\) 的。