信奥赛C++提高组csp-s之最小生成树算法Kruskal

信奥赛C++提高组csp-s之最小生成树算法Kruskal

一、Kruskal算法概述

Kruskal算法是一种用于求解最小生成树的贪心算法。最小生成树是一个无向连通图中，连接所有顶点且边权总和最小的树。

特点：

• 时间复杂度：O(E log E)，适合稀疏图
• 基于边的贪心算法
• 需要使用并查集数据结构

二、算法原理

核心思想：

1. 将图中所有边按权值从小到大排序
2. 按顺序选择边，如果这条边连接的两个顶点不在同一个连通分量中，则将其加入最小生成树
3. 重复步骤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算法）

1. 边排序：将所有边按权重从小到大排序
2. 并查集初始化：每个节点自成一个集合
3. 贪心选择：
   • 遍历排序后的边
   • 如果边的两个端点不在同一集合：
     • 合并两个集合
     • 累加边权重
     • 计数已选边数
4. 连通性检查：如果最终边数 ≠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;}

功能分析

算法步骤：

1. 输入处理：读取顶点数n、边数m，以及所有边的信息
2. 边排序：将所有边按权重从小到大排序
3. 并查集初始化：每个顶点初始时都是一个独立的集合
4. 贪心选择：按权重从小到大遍历每条边：
   • 如果边的两个端点不在同一连通分量中，选择该边
   • 合并这两个连通分量
   • 累加权重到总和中
5. 终止条件：
   • 成功：当选择了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;}