题目
先想 O ( n 2 ) O(n^2) O(n2) 的暴力：枚举任意两点以及所有边，用一个 c o n i , j con_{i,j} coni,j 数组记录补图中 i , j i,j i,j 间是否有边，用并查集或 bfs 判断连通块即可。记录
在给定边中，一个点的入度最小，那么在补图中他所在联通块最大，找到这个点。不难证明，这个点的入度至多 m n \dfrac m n nm，则不与该点一个联通块至多 m n \dfrac m n nm 个点，该点所在连通块至少有 ( n − m n ) (n - \dfrac m n) (n−nm) 个点。
由于 n , m ≤ 2 × 1 0 5 n,m \le 2 \times 10^5 n,m≤2×105， m n \dfrac m n nm 不会特别大。
解释：
具体来说， m n \dfrac {m} {n} nm 类似密度，图越稠密值越大。如果图足够稠密 m m m 最多大取 n ( n − 1 ) 2 ≤ 2 × 1 0 5 \dfrac {n(n-1)} {2} \le 2 \times 10^5 2n(n−1)≤2×105 ，得 n < 650 n < 650 n<650 左右，此时对应的 m n \dfrac {m} {n} nm 也就在 400 400 400 左右。
在找到这个点后，只有 400 400 400 个点在补图中与其不相连，其余点在补图中均与关键点直接有边相连，它们不论边的情况如何，都在关键点的联通块中。真正需要关注的是 400 400 400 多个点和其他点的边情况，这是可能对联通块情况造成影响的。对于 c o n con con 数组，我们只需开 400 × n 400 \times n 400×n。记录
