题解 | #加边的无向图#

一道并查集题，找出连通块个数，并用连通块数减一即得最小添加边数。

using namespace std;
const int mm=1e5+5;
 int n,m,a,b,p[mm],ans;
int find(int x){//找祖宗节点
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
int main(){
    cin>>n>>m;
    for(int i=0;i<=n;i++) p[i]=i;//初始化每个节点的根节点即本身
    while(m--){
        cin>>a>>b;
        if(find(a)!=find(b))////if语句如果不加上就判错？
            p[find(a)]=p[b];
    }
    for(int i=1;i<=n;i++){
        if(p[i]==i)  ans++;
    }
    cout<<ans-1<<en