信息
- ID
- 5894
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
容易想到计算每个点的时间戳 dfn。我们只需要找到一条边两个端点时间戳之差不小于 k,则这两点之间必有一条长度至少为 k 的简单路径,再加上一条直接连接两点的边,形成的整个环至少有 k+1 条边。
事实上任意一个符合每个点都至少连 k 条边这个条件的图,必然存在这样的简单环,证明也不困难。
证明: 显然存在一条简单路径 a1→a2→⋯→at 满足 at 所有边的另一个顶点都在 {a1, a2, ⋯,at} 中。设 ai 与 at 有连边的最小的 i 为 p,则由于 at 这个点至少连 k 条边,故 t−p+1≥k。那么只需取 ap→ap+1→⋯→at 就找到了一个简单环。