题解 | #NIT的图#

1.先把每个连通块变成一个完全图（不改变连通块数量）
2.将2个连通块合并最多可以连siz1*siz2条边（连通块少一个）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int n, m, q, y, p, e, cnt, a[N];
ll sum, h[N], x;
vector<int> v[N];
bool vis[N];
void dfs(int u) {
    vis[u] = 1;
    p++;
    for (auto i:v[u]) {
        e++;
        if (vis[i])continue;
        dfs(i);
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &q);
    while (m--) {
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i])continue;
        p = e = 0;
        dfs(i);
        e >>= 1;
        a[++cnt] = p;
        sum += (ll) p * (p - 1) / 2 - e;
    }
    sort(a + 1, a + 1 + cnt, greater<int>());
    int pre = 0;
    for (int i = 1; i < cnt; i++) {
        pre += a[i];
        h[i] = (ll) pre * a[i + 1];
    }
    for (int i = 1; i < cnt; i++)h[i] += h[i - 1];
    while (q--) {
        scanf("%lld", &x);
        if (x <= sum)printf("%d\n", cnt);
        else {
            x -= sum;
            int s = lower_bound(h + 1, h + cnt, x) - h;
            cout << max(1, cnt - s) << endl;
        }
    }
    return 0;
}