题解：判断图中是否存在等长简单环

问题分析

我们需要判断一个简单无向图中是否存在两个长度相同的简单环。这是一个经典的图论问题，关键在于高效地检测环的存在性并比较它们的长度。

算法思路

1. 图结构预处理

核心观察：如果图中环的数量足够多，根据鸽巢原理必然存在两个长度相同的环。

剪枝策略：

• 当 $m - n > 400$ 时，直接输出 Yes
• 这是因为在稀疏图中环的数量有限，但在较密图中环的数量会快速增长

2. 拓扑排序去除叶子节点

使用类似拓扑排序的方法去除度数为1的节点：

• 这些节点不可能出现在任何环中
• 不断删除度数为1的节点及其边，直到只剩下环和连接环的路径

3. 关键节点识别

识别图中的关键节点：

• 度数为3及以上的节点：多个环的交汇点
• 度数为2的节点：环上的节点
• 为这些关键节点分配唯一标识符

4. 环检测与长度计算

重构图：

• 将原图转换为以关键节点为顶点的新图
• 边权表示两个关键节点间的路径长度

环检测方法：

• 对每个关键节点作为起点进行DFS
• 记录从起点出发找到的环的长度
• 使用计数器 c[x] 统计每个环长度的出现次数

关键算法步骤

1. 图简化：去除叶子节点，保留环结构
2. 关键点标记：识别度≥2的节点作为关键节点
3. 路径压缩：将节点间路径压缩为带权边
4. 环长统计：DFS遍历统计所有环的长度
5. 结果判定：检查是否有环长度出现至少两次

复杂度分析

• 拓扑排序：$O(n + m)$
• 关键点识别：$O(n)$
• 环检测：$O(k^2)$，其中 $k$ 是关键节点数量
• 总复杂度：在数据范围内可行

算法优势

1. 剪枝优化：利用图密度快速判断多数情况
2. 图简化：去除无关节点，聚焦环结构
3. 关键点分析：减少问题规模，提高效率
4. 长度统计：直接统计环长出现频率

总结

本题的解法展示了如何将复杂的环检测问题转化为关键节点分析和路径压缩问题。核心创新点在于：

• 密度剪枝：利用 $m - n$ 关系快速处理稠密图
• 拓扑预处理：有效去除不影响环结构的节点
• 关键节点重构：将原图简化为更易处理的结构