#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 边结构体，包含起点、终点和权重
struct Edge {
int u, v, w;
bool operator<(const Edge& other) const {
return w < other.w;
}
};
// 并查集类
class UnionFind {
private:
vector<int> parent;
public:
UnionFind(int size) {
for (int i = 0; i < size; i++) {
parent.push_back(i);
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
};
// Kruskal算法实现
int kruskal(int V, vector<Edge>& edges) {
sort(edges.begin(), edges.end()); // 按权重排序
UnionFind uf(V);
int mstWeight = 0; // 最小生成树的权重
int e = 0; // 边数
for (Edge& edge : edges) {
int u = uf.find(edge.u);
int v = uf.find(edge.v);
if (u != v) { // 确保这条边不会形成环
uf.unite(u, v);
mstWeight += edge.w;
e++;
if (e == V - 1) break; // 最小生成树有V-1条边
}
}
if (e != V - 1) {
// 如果边数不足V-1，说明图不连通
return -1;
}
return mstWeight;
}
int main() {
int V = 4; // 顶点数
vector<Edge> edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5},
{1, 3, 15}, {2, 3, 4}};
int mstWeight = kruskal(V, edges);
if (mstWeight == -1) {
cout << "Graph is not connected" << endl;
} else {
cout << "Weight of MST is " << mstWeight << endl;
}
return 0;
}
