NC219798. NIT的图
描述
NIT 在 n 年前还是普及组选手的时候做过这样一个题目，求一个图的连通块数目，以NIT现在国家队的实力，做这样的题实在是太侮辱他的智商了，于是他思考着加强这道题目。
输入描述
输入共 m+q+1 行。
第一行 3 个 正整数 n,m,q ，分别表示点数，边数，操作数。
接下来 m 行，每行 2 个正整数 x,y 表示 x,y 之间有一条连边，无重边自环。
接下来 q 行，每行 1 个数为 x 表示在原图上加入 x 条边后最多有几个连通块，不允许加重边，自环，询问之间互不影响。
输出描述
你的输出应有 q 行，每行 1 个正整数 ans，表示这次询问的答案。
示例1
输入:
5 3 3 1 2 1 3 4 5 2 0 7
输出:
1 2 1
说明:
在原图上添加 2 条边时，无论怎样连边都会连成一个连通块，故答案为 1。示例2
输入:
7 4 5 6 4 7 1 3 1 5 2 5 8 1 10 17
输出:
2 1 3 1 1
C++ 解法, 执行用时: 318ms, 内存消耗: 13984K, 提交时间: 2021-06-19 19:15:48
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;
const int N=5e5+5;
int fa[N],sz[N],q[N],t;
s64 sum[N];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
#ifdef kcz
freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
int n,m,qcnt;
cin>>n>>m>>qcnt;
for(int i=1;i<=n;++i){
fa[i]=i;sz[i]=1;
}
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
x=find(x);y=find(y);
if(x!=y){
fa[x]=y;sz[y]+=sz[x];
}
}
for(int i=1;i<=n;++i)
if(fa[i]==i){
q[++t]=sz[i];
sum[1]+=sz[i]*s64(sz[i]-1)/2;
}
sort(q+1,q+t+1,greater<int>());
int s=0;
for(int i=2;i<=t;++i){
s+=q[i-1];
sum[i]=sum[i-1]+s*s64(q[i]);
}
while(qcnt--){
s64 x;
scanf("%lld",&x);
printf("%d\n",t-(lower_bound(sum+1,sum+t,m+x)-sum)+1);
}
}