容易想到计算每个点的时间戳 $dfn$。我们只需要找到一条边两个端点时间戳之差不小于 $k$，则这两点之间必有一条长度至少为 $k$ 的简单路径，再加上一条直接连接两点的边，形成的整个环至少有 $k+1$ 条边。

事实上任意一个符合每个点都至少连 $k$ 条边这个条件的图，必然存在这样的简单环，证明也不困难。

证明： 显然存在一条简单路径 $a_1\to a_2\to\cdots\to a_t$ 满足 $a_t$ 所有边的另一个顶点都在 $\{a_1,\ a_2,\ \cdots, a_t\}$ 中。设 $a_i$ 与 $a_t$ 有连边的最小的 $i$ 为 $p$，则由于 $a_t$ 这个点至少连 $k$ 条边，故 $t-p+1\geq k$。那么只需取 $a_p\to a_{p+1}\to\cdots\to a_t$ 就找到了一个简单环。