加边的无向图

核心算法：并查集
并查集，并查集，顾名思义：就是查询与合并；
首先是查：

int find(int x){
    //有两种写法：
//一:if(fa[x]==x)return x;
//else return fa[x]=find(fa[x]);
//二就是利用三目运算符进行压行；
    return fa[x]==x?x:fa[x]=find(fa[x]); 
}

然后合并

int merge(int x,int y){
    //找到x，y的最终的父亲，将其中一个的父亲变成另一个的儿子；
    int fx=find(x);
    int fy=find(y);
    fa[fy]=fx;//这就是将y的父亲变成了x的儿子； 
//当然这三句话也可以合并成一句话
//fa[find(x)]=find(y);
}

别的就不多说，ac代码如下

#include<iostream>
#include<algorithm>
using namespace std;
#define N 1000000
int fa[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int main(){
    int m,n;
    cin>>m>>n;
    int a,b;
    for(int i=1;i<=m;i++)fa[i]=i;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        merge(a,b);
    }
    int ans=0;
    for(int i=1;i<=m;i++)if(fa[i]==i)ans++;
//因为我们得到的ans是其中链接起来的区块的个数，而我们要将他们全部连起来就需要ans-1个边
    cout<<ans-1<<endl;
    return 0;
}