当前位置：首页 > 洛谷 > 洛谷1111题解题全解析：基于Kruskal算法与并查集的最小生成树实现

洛谷1111题解题全解析：基于Kruskal算法与并查集的最小生成树实现

2个月前 (06-15)

一、题目解读

洛谷1111题是一道经典的图论问题，要求构建一个无向图的最小生成树，并输出其最大边权值。题目核心在于通过给定的边集合，找到连接所有节点的最小权值子集，同时保证无环。这通常涉及最小生成树算法（如Kruskal）的应用，需要高效处理边权重与节点连通性。

二、解题思路

代码采用Kruskal算法与并查集的结合，巧妙解决最小生成树问题。其核心思路为：

1. 贪心策略：按边权重递增排序，优先选择权值最小的边；

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;
}