最小生成树kruskal算法题目

### Kruskal算法实现最小生成树的练习题

#### 题目描述
给定一个无向加权连通图，使用Kruskal算法求解该图的最小生成树，并计算最小生成树中所有边的权重之和。

#### 输入格式
第一行为两个整数`n` 和 `m` (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 3 * 10^5)，分别表示顶点的数量和边的数量。接下来有`m` 行，每一行包含三个整数`u`, `v` 和 `w` (1 ≤ u,v ≤ n, 1 ≤ w ≤ 10^9)，表示连接顶点`u` 和顶点`v` 的一条边及其权重`w`。

#### 输出格式
仅一行，即最小生成树中的所有边的权重之和。

#### 示例代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int src, dest, weight;
};

class DisjointSet {
private:
    vector<int> parent, rank;
public:
    DisjointSet(int size) : parent(size), rank(size, 0) {
        for (int i = 0; i < size; ++i)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    void Union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY])
                parent[rootY] = rootX;
            else if (rank[rootX] < rank[rootY])
                parent[rootX] = rootY;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

bool compare(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

long long kruskalMST(vector<Edge>& edges, int V) {
    sort(edges.begin(), edges.end(), compare); // 对所有的边按照其权重升序排列[^2]

    DisjointSet ds(V);
    long long result = 0;
    int count = 0;

    for (auto edge : edges) {
        int x = ds.find(edge.src);
        int y = ds.find(edge.dest);

        if (x != y) { // 如果这条边不会形成环，则加入到当前森林中
            result += edge.weight;
            ds.Union(x, y);
            count++;
            if (count == V - 1) break; // 当前已经包含了V-1条边，说明形成了最小生成树
        }
    }

    return result;
}