题解 P4350 【[CERC2015]Export Estimate】

JoshAlMan · 2020-12-20 12:49:00 · 题解

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

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

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

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

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

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

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

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

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

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