关于最小生成树的基础模版

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

using namespace std;

// 定义边的结构体
struct Edge {
    int u, v, w; // 边的起点、终点和权重
};

// 比较函数，用于排序边
bool operator<(const Edge&amp; a, const Edge&amp; b) {
    return a.w < b.w;
}

// 并查集的父节点数组
int parent[100005];

// 查找根节点
int find(int x) {
    return parent[x] = find(parent[x]);
}

// 合并两个集合
void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) parent[px] = py;
}

int main() {
    int n, m; // n为顶点数，m为边数
    cin >> n >> m;
    
    // 读取所有边
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    
    // 按照边的权重排序
    sort(edges.begin(), edges.end());
    
    // 初始化并查集
    for (int i = 0; i <= n; i++) parent[i] = i;
    
    long long ans = 0; // 最小生成树的总权重
    int cnt = 0; // 已经加入最小生成树的边数
    
    // 遍历所有边
    for (auto&amp; e : edges) {
        int pu = find(e.u), pv = find(e.v);
        if (pu != pv) {
            merge(pu, pv);
            ans += e.w;
            cnt++;
        }
        if (cnt == n - 1) break; // 如果已经加入 n-1 条边，停止
    }
    
    // 输出结果
    if (cnt == n - 1) {
        cout << ans << endl;
    } else {
        cout << &quot;IMPOSSIBLE&quot; << endl; // 如果无法形成最小生成树
    }

    return 0;
}