（测试题解）

(注：此文设题中输入的图为 $G_1$，对应的完全图为 $G_2$，对应的补图为 $G_3$)

首先不难想到暴力思路：直接将 $G_2$ 建出来，跑一遍 MST 即可。

然而这样时间显然无法承受。

但是这道题显然有别的思路，考虑从特殊的边长：$0$ 和 $1$ 入手。

题中所给的边长为 $1$ 的边视为断边，建出 $G_3$，不难发现，答案就是补图的连通块数量减 $1$。

我们只需要算出连通块的数量即可，可以用并查集处理。

然而边数仍然很多，直接暴力求连通块很容易 TLE/MLE。

这时这个题目巧妙的地方就来了：我们可以将求解拆成两块，再合并答案。

首先发现，在原图 $G_1$ 中，设点 $i$ 的度数为 $deg_i$，不难发现$\sum\limits_{i=1}^n deg_i =2m$

那么根据抽屉原理，其中度数最小的点度数不超过 $\frac{2m}{n}$ ，设该点为 $u$ .

则可以先将 $G_1$ 中与 $u$ 没有连边的点和 $u$ 暴力合并，和 $u$ 有连边的点存储下来，暴力合并。

其中暴力合并的复杂度为 $O(N)$，则整体的时间复杂度为 $O(N+N\times \frac{2m}{N})=O(N+M)$.