洛谷1111题解题全解析：基于Kruskal算法与并查集的最小生成树实现
3个月前 (06-15)
一、题目解读
洛谷1111题是一道经典的图论问题，要求构建一个无向图的最小生成树，并输出其最大边权值。题目核心在于通过给定的边集合，找到连接所有节点的最小权值子集，同时保证无环。这通常涉及最小生成树算法（如Kruskal）的应用，需要高效处理边权重与节点连通性。
二、解题思路
代码采用Kruskal算法与并查集的结合，巧妙解决最小生成树问题。其核心思路为：
2. 连通性判断：利用并查集快速合并节点，避免形成环。
通过这两个关键步骤，算法能在O(ElogE)复杂度下高效求解。
三、解题步骤
1. 输入与初始化：
读取节点数N和边数M，创建边集合edges；
初始化并查集parent数组（每个节点初始为自身根节点）。
2. 边排序：对edges按权值t升序排序，确保后续按权重递增处理。
3. 核心循环：遍历每条边，执行合并操作：
通过find函数获取边两端节点的真实根节点；
若根节点不同，合并节点并更新最大边权值max_t。
4. 结果判断：若合并次数达到N-1（即形成一棵树），输出max_t；否则输出-1（图不连通）。
四、代码与注释
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 边结构（节点u、v及权值t）
struct Edge {
int u, v, t;
bool operator<(const Edge& other) const {
return t < other.t; // 按权值排序比较函数
}
};
vector<int> parent; // 并查集：记录节点的根节点
// 查找节点x的根节点（路径压缩优化）
int find(int x) {
return parent[x] == x? x : parent[x] = find(parent[x]);
}
// 合并节点x与y，返回是否成功（避免环）
bool unite(int x, int y) {
x = find(x); // 获取x的根
y = find(y); // 获取y的根
if(x == y) return false; // 同根则不合并
parent[y] = x; // 合并y到x
return true;
}
int main() {
int N, M;
cin >> N >> M;
vector<Edge> edges(M);
parent.resize(N+1); // 初始化并查集数组
// 初始化：每个节点为独立根节点
for(int i=1; i<=N; i++) parent[i] = i;
// 输入边信息
for(int i=0; i<M; i++)
cin >> edges[i].u >> edges[i].v >> edges[i].t;
// 按权值排序
sort(edges.begin(), edges.end());
int cnt = 0, max_t = 0; // 合并次数与最大边权
for(auto& e : edges) {
// 若合并成功且未形成完整树，更新信息
if(unite(e.u, e.v)) {
max_t = max(max_t, e.t);
if(++cnt == N-1) break; // 树已生成，退出循环
}
}
// 根据连通性输出结果
cout << (cnt == N-1? max_t : -1) << endl;
return 0;
}五、总结
本解法通过Kruskal算法与并查集的深度融合，实现了高效的最小生成树构建。其优势在于：
1. 时间复杂度优化：排序+并查集降低处理复杂度；
2. 代码简洁性：结构清晰，逻辑易懂，适合竞赛与工程场景。
该思路为同类图论问题提供了通用解决方案，尤其在稀疏图环境中表现优异。
原创内容 转载请注明出处
