cxy 好可爱

tzl_Dedicatus545 · 2025-06-19 22:54:59 · 题解

一年前的联考怎么被搬到洛谷了。

首先我们对于所有节点对 (u,v) 求出于 u 和 v 都有连边的节点个数 b_{u,v}，不难发现存在四元环等价于某个 b_{u,v}\geq 2。

显然在改变边时 b 是容易维护的，接下来只需维护初始的即可。

显然我们可以在 \sum \text{deg}_u \choose 2 的复杂度里去维护。考虑四元环是很容易存在的。我们给出如下引理：

若 \sum \binom{\text{deg}_u}{2} > \binom{n}{2}，则图中一定存在四元环。

证明考虑抽屉原理。

故可以在 O(n^2+nq) 的时间复杂度内简单维护。