题解：洛谷 P14077 [GESP202509 七级] 连通图

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P14077 [GESP202509 七级] 连通图 - 洛谷

【题目描述】

给定一张包含n nn个结点与m mm条边的无向图，结点依次以1 , 2 , … , n 1,2,…,n1,2,…,n编号，第i ii条边（1 ≤ i ≤ m 1≤i≤m1≤i≤m）连接结点u i u_iui​与结点v i v_ivi​。如果从一个结点经过若干条边可以到达另一个结点，则称这两个结点是连通的。

你需要向图中加入若干条边，使得图中任意两个结点都是连通的。请你求出最少需要加入的边的条数。

注意给出的图中可能包含重边与自环。

【输入】

第一行，两个正整数n , m n,mn,m，表示图的点数与边数。

接下来m mm行，每行两个正整数u i , v i u_i,v_iui​,vi​，表示图中一条连接结点u i u_iui​与结点v i v_ivi​的边。

【输出】

输出一行，一个整数，表示使得图中任意两个结点连通所需加入的边的最少数量。

【输入样例】

4 4 1 2 2 3 3 1 1 4

【输出样例】

0

【算法标签】

#普及-# #并查集#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 定义最大节点数intn;// 节点数量intm;// 边数量intans=0;// 存储连通分量数量intp[N];// 并查集父节点数组boolvis[N];// 标记数组，记录是否已统计过该连通分量/** * 并查集查找函数（带路径压缩） * @param x 要查找的节点 * @return 节点x的根节点 */intfind(intx){if(p[x]!=x)// 如果当前节点不是根节点{p[x]=find(p[x]);// 路径压缩}returnp[x];}intmain(){// 输入节点数和边数cin>>n>>m;// 初始化并查集，每个节点的父节点指向自己for(inti=1;i<=n;i++){p[i]=i;}// 处理每条边，合并连通分量while(m--){inta,b;cin>>a>>b;// 合并a和b所在的连通分量p[find(a)]=find(b);}// 统计连通分量数量for(inti=1;i<=n;i++){intx=find(i);// 找到节点i的根节点if(!vis[x])// 如果该连通分量未被统计过{ans++;// 连通分量数量加1vis[x]=1;// 标记该连通分量已统计}}/** * 输出结果： * 连通分量数量减1，即需要添加的边数 * 因为要将所有连通分量连接成一棵树需要ans-1条边 */cout<<ans-1<<endl;return0;}

【运行结果】

4 4 1 2 2 3 3 1 1 4 0