题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
输入格式
第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 Xi,Yi,Zi，表示有一条长度为 Zi 的无向边连接结点 Xi,Yi。
输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
输入 #1复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
输出 #1复制
7
说明/提示
数据规模：
对于 20% 的数据，N≤5，M≤20。
对于 40% 的数据，N≤50，M≤2500。
对于 70% 的数据，N≤500，M≤104。
对于 100% 的数据：1≤N≤5000，1≤M≤2×105，1≤Zi≤104。
样例解释：
所以最小生成树的总边权为 2+2+3=7。
代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 边的结构：起点、终点、权值
struct Edge {
int u, v, w;
Edge(int u_, int v_, int w_) : u(u_), v(v_), w(w_) {}
// 用于排序，按权值从小到大
bool operator<(const Edge& other) const {
return w < other.w;
}
};
// 并查集数据结构，用于判断连通性
class UnionFind {
private:
vector<int> parent;
vector<int> rank;
public:
UnionFind(int n) {
parent.resize(n + 1); // 节点编号从1开始
rank.resize(n + 1, 0);
for (int i = 1; i <= n; ++i) {
parent[i] = i;
}
}
// 查找根节点
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
// 合并两个集合
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return; // 已经在同一个集合
// 按秩合并
if (rank[x] < rank[y]) {
parent[x] = y;
} else {
parent[y] = x;
if (rank[x] == rank[y]) {
rank[x]++;
}
}
}
// 判断两个节点是否连通
bool isConnected(int x, int y) {
return find(x) == find(y);
}
};
int main() {
int N, M;
cin >> N >> M;
vector<Edge> edges;
for (int i = 0; i < M; ++i) {
int x, y, z;
cin >> x >> y >> z;
edges.push_back(Edge(x, y, z));
}
// 按权值排序
sort(edges.begin(), edges.end());
UnionFind uf(N);
int totalWeight = 0;
int edgesUsed = 0;
// 使用传统for循环遍历所有边，构建最小生成树
for (int i = 0; i < edges.size(); ++i) {
const Edge& e = edges[i];
if (!uf.isConnected(e.u, e.v)) {
uf.unite(e.u, e.v);
totalWeight += e.w;
edgesUsed++;
// 最小生成树有n-1条边
if (edgesUsed == N - 1) {
break;
}
}
}
// 检查是否所有节点都连通
if (edgesUsed == N - 1) {
cout << totalWeight << endl;
} else {
cout << "orz" << endl;
}
return 0;
}