首先将题意转化一下，假设我们在第一步中将原图划分成了 \(p\) 个连通块，计第 \(i\) 连通块大小为 \(siz_i\)，那么每个连通块可以向外连 \(\min{(k,a_i)}\) 条边。而使原图联通显然至少需要 \(p-1\) 条边，形式话的来讲，我们能在第二步使图联通这个条件等价于 \(\sum{\min {(siz_i,k)}} \ge 2(p-1)\)。
这样的话我们再来考虑第一步，我们需要最大化左边，最小化右边。此时由于这个式子只与各个联通块的大小和连通块的数量有关，我们可以用并查集求出初始图的连通块信息，将加边操作转化为联通块的合并，联通块合并使用优先队列维护即可，时间复杂度 \(O(m+n\log{n})\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
inline int read(){
int f=1,w=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=(w<<1)+(w<<3)+(c^48);
c=getchar();
}
return f*w;
}
int fa[N];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
fa[x]=y;
}
int a[N];
int n,m,k;
priority_queue <int, vector<int> , greater <int> > q;
int main(){
n=read();
m=read();
k=read();
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
int x,y;
x=read();
y=read();
merge(x,y);
}
for(int i=1;i<=n;i++){
a[find(i)]++;
}
int cnt=0;
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]){
q.push(a[i]);
cnt++;
ans+=min(a[i],k);
}
}
if(ans>=2*(cnt-1)){
printf("0\n");
return 0;
}
int res=0;
while(q.size()>=2){
int x=q.top();
q.pop();
int y=q.top();
q.pop();
cnt--;
ans-=min(x,k);
ans-=min(y,k);
ans+=min(x+y,k);
res++;
if(ans>=2*(cnt-1)){
break;
}
q.push(x+y);
}
cout<<res<<endl;
return 0;
}