自动搬运

查看原文

来自洛谷，原作者为

	kkksc03 洛谷吉祥物 DA✩ZE

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

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

以下是正文

By tinylic

经过找规律可以发现答案为n-2.

以下是证明：

令d[i]为i 的度数。

考虑一个点i 不被删去的条件，必然是前面与i 相邻的点j（可以是多个）被删去，导致d[i]

减小至小于等于d[j].

1)易知ans!=n。

2)考虑ans能否是n-1，也就是只删一个点，设这个点为i。

因为i 是唯一被删去的点，所以d[i]一定不是最大的，即d[i]<n-1。

其次删去i 导致其余点的d[]均发生改变，从而无法被删去。

即i 和其余点都相连，d[i]=n-1，矛盾。

所以ans!=n-1.

3)我们可以构造出ans=n-2的情况：

构造完全图G,删去一条边(i,j)。这样d[i]=d[j]=n-2,其余d[]均为n-1.

首先删去VI,Vj，这样其余点各少两条边，d[]均变成n-3,不用被删去。

由此n-2是合法的解，也是最大的解，所以答案就是n-2.