自动搬运

查看原文

来自洛谷，原作者为

	JoshAlMan i人

搬运于2025-08-24 21:59:16，当前版本为作者最后更新于2020-12-20 12:49:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

发现两种操作均不影响每个点的度数，第二个操作可以看作把一个点连向两个点转化成了一个边。

而点边的删除的条件都是点的度数，因此考虑点的顺序并不影响图的结构，只会影响删除/留下点的编号，但这个东西对我们没用。

那么我们就可以用一个经典的思路，把边从大到小排序，依此插入边，考虑当前的图对应的点边结构是多少，然后加入那些处于这个状态的答案。我们考虑何种情况的一个点会被删除：

• 度数 $= 0$ 的点。
• 度数 $= 2$ 的点且最终状态并不是一个自环。并不是一个自环的条件只能在纯粹的环（即所处联通块只有一个简单环，没有其他冗余的东西）中取到，想象一下它会以此把编号最小的点换成一条边，最终会留下一个编号最大的点的自环。而其他情况，不可能出现度数为 $2$ 的点连的是自环的情况，如果不构成一个环，那么原来图里没自环，连接的两个方向点必不可能缩成同一个点（大小为 $2$ 的纯粹环）。如果构成一个环，但环上有其他杂边，那么不会缩成只有一个点，因为必然有一个点度数 $> 2$。

因此最终状态点的数量 $=$ $n\ -$ 度数为 $0$ 的点数 $-$ 度数为 $2$ 的点数 $+$ 纯粹的环数

然后再考虑何种情况边的数量会改变：

• 度数 $= 2$ 的点且最终状态并不是一个自环 的点，会让两条边数变成一条边，道理同上。

因此最终状态点的数量 $=$ $m\ -$ 度数为 $2$ 的点数 $+$ 纯粹的环数。

其他东西维护都比较简单，纯粹的环数等价于该联通块每个点度数 $= 2$。用一个并查集维护联通块中度数为 $2$ 的点数就好了。

时间复杂度可以做到线性（不排序，用桶，并查集两个优化做到常数）。