题解 | #加边的无向图#

思路

我们知道，要让n个点联通，就要用n-1条边。
Kruskal求最小生成树用到的边数num，
那么缺的边数就是n-1-num。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct E{
    int from,next,to;
}edge[maxn*2];

int head[maxn],cnt=0;
int n,m,u,v, num=0,fa[maxn];

void addedge(int from,int to){
    edge[++cnt].next=head[from];
    edge[cnt].from=from;
    edge[cnt].to=to;
    head[from]=cnt;
}

int find(int x){
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}

void unite(int x,int y){
    fa[find(x)]=find(y);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=1;i<=cnt;i++){
        if(find(edge[i].from)!=find(edge[i].to)){
            unite(edge[i].from,edge[i].to);
            num++;
        }
    }
    cout<<n-num-1<<endl;
    return 0;
}