信奥赛C++提高组csp-s之最小生成树算法Kruskal
一、Kruskal算法概述
Kruskal算法是一种用于求解最小生成树的贪心算法。最小生成树是一个无向连通图中，连接所有顶点且边权总和最小的树。
特点：
- 时间复杂度：O(E log E)，适合稀疏图
- 基于边的贪心算法
- 需要使用并查集数据结构
二、算法原理
核心思想：
- 将图中所有边按权值从小到大排序
- 按顺序选择边，如果这条边连接的两个顶点不在同一个连通分量中，则将其加入最小生成树
- 重复步骤2直到选择了n-1条边（n为顶点数）
研究案例：最小生成树
题目说明
给定一个无向图，包含n nn个节点和m mm条边，求最小生成树的权重和。如果图不连通，输出"orz"。
输入格式
- 第一行：两个整数n nn（节点数）和m mm（边数）
- 接下来m mm行：每行三个整数u , v , w u, v, wu,v,w，表示节点u uu和v vv之间有一条权重为w ww的无向边
输出格式
- 一个整数：最小生成树的权重和
- 如果图不连通，输出
orz
样例输入
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3样例输出
7数据规模
- 1 ≤ n ≤ 5000 1 \leq n \leq 50001≤n≤5000
- 1 ≤ m ≤ 2 × 10 5 1 \leq m \leq 2 \times 10^51≤m≤2×105
- 1 ≤ w ≤ 10 4 1 \leq w \leq 10^41≤w≤104
算法思路（Kruskal算法）
- 边排序：将所有边按权重从小到大排序
- 并查集初始化：每个节点自成一个集合
- 贪心选择：
- 遍历排序后的边
- 如果边的两个端点不在同一集合：
- 合并两个集合
- 累加边权重
- 计数已选边数
- 连通性检查：如果最终边数 ≠n − 1 n-1n−1，输出
orz
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,m;// n个顶点，m条边// 边的结构体，存储每条边的两个端点和权重structnode{intx,y,w;// 边连接的两个顶点x,y，边的权重w}a[200010];// 最多200000条边// 比较函数，用于将边按权重从小到大排序boolcmp(node a,node b){returna.w<b.w;}intfa[5010];// 并查集数组，用于记录每个顶点的父节点// 并查集的查找函数，带路径压缩intfind(intx){if(fa[x]!=x)returnfa[x]=find(fa[x]);// 路径压缩returnfa[x];}// 并查集的合并函数voidunionSet(intx,inty){introotx=find(x);introoty=find(y);if(rootx==rooty)return;// 已经在同一集合中，不需要合并fa[rooty]=rootx;// 合并两个集合}intmain(){cin>>n>>m;// 输入所有边的信息for(inti=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].w;}// 将边按权重从小到大排序sort(a+1,a+m+1,cmp);// 初始化并查集，每个顶点自成一个集合for(inti=1;i<=n;i++){fa[i]=i;}intsum=0;// 最小生成树的总权重intcnt=0;// 已选边的数量// Kruskal算法核心：遍历所有边for(inti=1;i<=m;i++){// 如果当前边的两个端点不在同一连通分量中if(find(a[i].x)!=find(a[i].y)){unionSet(a[i].x,a[i].y);// 合并两个连通分量sum+=a[i].w;// 累加权重cnt++;// 边数加1// 如果已选边数达到n-1，说明最小生成树已完成if(cnt==n-1){cout<<sum;return0;}}}// 如果循环结束但边数不足n-1，说明图不连通cout<<"orz";return0;}功能分析
算法步骤：
- 输入处理：读取顶点数n、边数m，以及所有边的信息
- 边排序：将所有边按权重从小到大排序
- 并查集初始化：每个顶点初始时都是一个独立的集合
- 贪心选择：按权重从小到大遍历每条边：
- 如果边的两个端点不在同一连通分量中，选择该边
- 合并这两个连通分量
- 累加权重到总和中
- 终止条件：
- 成功：当选择了n-1条边时，输出总权重
- 失败：如果遍历完所有边但边数不足n-1，输出"orz"表示图不连通
关键特点：
- 时间复杂度：O(M log M)，主要由排序决定
- 空间复杂度：O(N + M)
- 适用性：适合稀疏图（边数相对较少的情况）
- 正确性保证：通过并查集确保不会形成环，通过贪心选择保证权重最小
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、csp高频考点知识详解及案例实践：
- CSP信奥赛C++之动态规划
- CSP信奥赛C++之标准模板库STL
- 信奥赛C++提高组csp-s知识详解及案例实践
- 四、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、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
4、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
