自动搬运

查看原文

来自洛谷，原作者为

	tzl_Dedicatus545 忙碌着 无为着 继续

搬运于2025-08-24 23:17:34，当前版本为作者最后更新于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)$ 的时间复杂度内简单维护。