本文采用 1-index。

对于点 $i$，维护 $[1,k]$ 中可以到达它的点中编号最大值 $l_i$，及它可以到的点中编号最小值 $r_i$。最开始，$[1,k]$ 中的点 $i$ 有 $(l_i,r_i)=(i,i)$，其他点有 $(l_i,r_i)=(0,k+1)$。如果在某时刻，有 $i>k$ 的点满足 $l_i \ge r_i$，则说明出现了环。

如果在加边时，直接根据定义，暴力地 dfs 更新每个点的 $l_i,r_i$，加入优化「如果一个点的 $l,r$ 均未更新，则不再 dfs 下去」后复杂度为 $O(k(n+m))$。原因是每个点的 $l,r$ 最多改变 $k$ 次。

对 $[1,k]$ 建立线段树，考虑所有节点对应的区间集。设 $S[l,r]$ 为区间集中最小的包含 $[l,r]$ 的区间。我们转而维护每个点 $i$ 对应的 $S[l_i,r_i]$，而不是 $l_i,r_i$ 本身。

讨论一下添加（或更新）边 $u \to v$ 的情况：

• 若 $l_u \geq r_v$，则已成环。
• 若 $S[l_v, r_v] \subseteq \operatorname{lson}(S[l_u, r_u])$，则令 $S[l_u, r_u] \leftarrow \operatorname{lson}(S[l_u, r_u])$ 并去尝试更新与 $u$ 有关的其他边。
• 若 $S[l_u, r_u] \subseteq \operatorname{rson}(S[l_v, r_v])$，则令 $S[l_v, r_v] \leftarrow \operatorname{rson}(S[l_v, r_v])$ 并去尝试更新与 $v$ 有关的其他边。

若全部更新完，仍没有出现第一种情况，则可以证明仍未有环。

由于一个区间最多下放 $O(\log k)$ 次，故时间复杂度 $O((n+m)\log k)$。