Kruskal易错因排序失效和并查集未优化：边须权重前置或自定义比较，UF必须路径压缩，验证需检查选边数是否为n-1且图连通。
为什么直接写 Kruskal 常常连边都排不对？
因为 std::sort 默认按第一个字段升序，而你传的边结构体或 std::tuple 如果没重载比较或写错 compare，排序就失效。常见错误是把权重放在结构体第二个字段却没自定义排序规则，结果算法从最大边开始选，根本得不到最小生成树。
推荐统一用 std::vector<:tuple int>> 存边：权重在前，sort 自然按权重升序；或者用结构体 + lambda：
std::vectoredges; std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.weight < b.weight; });
并查集（Union-Find）不路径压缩会超时吗？
会。尤其点数 > 1e4 时，朴素 find 可能退化成 O(n) 单次查询，整体复杂度接近 O(mn)，Kruskal 就失去意义。必须做路径压缩 + 按秩合并（或只做路径压缩也够大多数 OJ 场景）。
关键实现要点：
立即学习“C++免费学习笔记（深入）”；
-
parent[i] = i初始化不能漏 -
find中递归调用后要赋值更新：return parent[x] = find(parent[x]) -
unionSet里判断的是rootA != rootB，不是a != b
struct UnionFind {
std::vector parent, rank;
UnionFind(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool unionSet(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (rank[ra] < rank[rb]) std::swap(ra, rb);
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
return true;
}
}; 输入边时顶点编号从 0 还是 1 开始？
取决于题干。国内 OJ（如洛谷、PTA）多数用 1-indexed 顶点，但 UnionFind 类内部下标是 0-based，所以读入后立刻减 1，别等到排序或合并时再处理——容易忘、易出界、调试困难。
例如输入 u v w，统一转成：
int u, v, w; std::cin >> u >> v >> w; edges.emplace_back(w, u - 1, v - 1); // 权重前置，顶点归零
后续所有 unionSet(u-1, v-1)、find(u-1) 都基于 0-indexed，逻辑干净。
如何验证 Kruskal 输出的边确实构成 MST？
最简验证方式：检查是否恰好选了 n - 1 条边，且总权重与标准答案一致。更稳妥的做法是，在每次 unionSet 成功后记录该边，并确保最终 result.size() == n - 1；若提前结束（边用完但没凑够），说明图不连通——这时应返回错误或输出 -1，而不是强行输出部分结果。
典型收尾逻辑：
int cnt = 0, totalWeight = 0;
for (auto [w, u, v] : edges) {
if (uf.unionSet(u, v)) {
totalWeight += w;
cnt++;
if (cnt == n - 1) break;
}
}
if (cnt != n - 1) {
std::cout << "-1\n"; // 不连通
} else {
std::cout << totalWeight << "\n";
}注意：不要在循环外再查 uf.find(0) == uf.find(i) 判断连通性——Kruskal 过程中已隐含该信息，重复检查无必要且易错。
真正容易被忽略的是：当存在多条相同权重的边时，sort 的稳定性不影响正确性，但不同实现可能选出不同的 MST（只要总权相等就合法）。如果题目要求输出字典序最小的边集，就得在权重相同时按端点二次排序——这点几乎没人提，但现场笔试真会卡。
