海东市网站建设_网站建设公司_小程序网站_seo优化

2025年9月GESP真题及题解(C++七级): 连通图

题目描述

给定一张包含n nn个结点与m mm条边的无向图，结点依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号，第i ii条边（1 ≤ i ≤ m 1\le i\le 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​的边。

输出格式

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

输入输出样例 1

输入 1

4 4 1 2 2 3 3 1 1 4

输出 1

0

输入输出样例 2

输入 2

6 4 1 2 2 3 3 1 6 5

输出 2

2

说明/提示

对于40 % 40\%40%的测试点，保证1 ≤ n ≤ 100 1\le n\le 1001≤n≤100，1 ≤ m ≤ 100 1\le m\le 1001≤m≤100。

对于所有测试点，保证1 ≤ n ≤ 10 5 1\le n\le 10^51≤n≤105，1 ≤ m ≤ 10 5 1\le m\le 10^51≤m≤105。

思路分析

这是一个连通分量计数问题。要让整个图连通，我们需要将图中所有连通分量连接起来。

关键点：

1. 如果图已经是连通的（只有1个连通分量），则不需要加边 → 答案为0
2. 如果有k个连通分量，最少需要k-1条边将它们连接成连通图
3. 重边和自环不影响连通性判断

解题步骤：

1. 使用**并查集(Union-Find)**统计连通分量数量
2. 答案 = 连通分量数量 - 1

复杂度分析：

• 并查集：O(m·α(n))，其中α是反阿克曼函数，近似常数
• DFS/BFS：O(n + m)
• 本题n,m ≤ 10^5，两种方法都可行

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100005;// 并查集数组intparent[MAXN];intsize[MAXN];// 初始化并查集voidinit(intn){for(inti=1;i<=n;i++){parent[i]=i;// 每个节点的父节点初始为自己size[i]=1;// 每个集合的大小初始为1}}// 查找根节点（带路径压缩）intfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);// 路径压缩，直接指向根节点}returnparent[x];}// 合并两个节点所在的集合（按秩合并）voidunite(intx,inty){introotX=find(x);introotY=find(y);// 如果已经在同一集合，无需合并if(rootX==rootY)return;// 按大小合并：将小集合合并到大集合if(size[rootX]<size[rootY]){parent[rootX]=rootY;size[rootY]+=size[rootX];}else{parent[rootY]=rootX;size[rootX]+=size[rootY];}}intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,m;cin>>n>>m;// 初始化并查集init(n);// 处理每条边for(inti=0;i<m;i++){intu,v;cin>>u>>v;unite(u,v);// 合并两个节点所在的连通分量}// 统计连通分量数量intcomponents=0;for(inti=1;i<=n;i++){// 如果节点的父节点是自己，说明它是一个连通分量的根if(parent[i]==i){components++;}}// 需要添加的边数 = 连通分量数 - 1cout<<components-1<<endl;return0;}

功能分析

数据结构：

• parent[i]: 存储节点i的父节点
• size[i]: 存储以i为根的集合大小（用于按秩合并）

核心函数：

1. init(n):

   • 初始化并查集
   • 每个节点自成一个集合

2. find(x):

   • 查找x所在集合的根节点
   • 使用路径压缩优化：将查询路径上的节点直接指向根节点
   • 均摊时间复杂度O(α(n))，近似常数

3. unite(x, y):

   • 合并x和y所在的集合
   • 使用按大小合并优化：将小集合合并到大集合
   • 避免树退化成链，保证查询效率

主流程：

1. 读取n和m
2. 初始化并查集
3. 逐条边读入并合并两个端点所在的连通分量
   • 注意：重边和自环会被unite函数正确处理（自环的u==v会直接返回，重边会重复合并同一集合）
4. 统计连通分量数量
   • 遍历所有节点，统计根节点数量（parent[i]==i）
5. 输出结果：components - 1

复杂度：

• 时间复杂度：O(m·α(n) + n)，其中α(n)是反阿克曼函数，非常小（≤5）
• 空间复杂度：O(n)

示例验证：

示例1：

输入： 4 4 1 2 2 3 3 1 1 4

• 所有节点连通 → 1个连通分量
• 答案 = 1 - 1 = 0

示例2：

输入： 6 4 1 2 2 3 3 1 6 5

• 连通分量1：{1,2,3}
• 连通分量2：{4}（孤立节点）
• 连通分量3：{5,6}
• 共3个连通分量
• 答案 = 3 - 1 = 2

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}