需先用std::sort按权值w升序排序边，再用带路径压缩和按秩合并的并查集实现Kruskal：遍历排序后边，若两端点不连通则合并并累加权值，选满n-1条边即停。
怎么用 std::sort 对边按权值升序排序
边必须先排好序，Kruskal 才能贪心地从小到大选边。C++ 中最直接的方式是把边存成 struct 或 tuple，然后传自定义比较函数给 std::sort。
- 推荐用
struct Edge { int u, v, w; };，语义清晰，避免tuple的位置混淆 - 比较函数要写成 lambda 或独立函数，不能只靠
operator（除非你重载了） - 务必按
w升序，否则算法失效；若权值相同，顺序不影响正确性，但可加次级排序避免潜在不稳定
struct Edge {
int u, v, w;
};
vector edges;
// ... 添加边
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.w < b.w;
}); 并查集（Union-Find）怎么写才不超时、不写错
Kruskal 的核心是快速判断两点是否已连通，并合并集合。手写并查集必须带路径压缩 + 按秩合并，否则在稀疏图上可能退化到 O(m log n) 甚至更差。
-
parent[i]初始为i，rank[i]初始为 0（或用 size 启发式） -
find(x)必须递归/迭代做路径压缩，不能只返回根而不更新 -
unionSets(a, b)要先find再比秩，不能直接对原始下标操作 - 注意：节点编号通常从 0 或 1 开始，初始化大小要对齐（比如
n+1）
struct UnionFind {
vector parent, rank;
UnionFind(int n) : parent(n), rank(n, 0) {
iota(parent.begin(), parent.end(), 0);
}
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]) swap(x, y);
parent[y] = x;
if (rank[x] == rank[y]) rank[x]++;
}
}; 怎么组装 Kruskal 主循环：边遍历 + 并查集判环 + 累加权值
主逻辑极简：遍历已排序的边，对每条边 (u, v, w)，若 find(u) != find(v)，就合并并加进 MST；否则跳过（成环）。
- 用一个计数器
edges_used控制何时退出：MST 只需n-1条边，满即停 - 不要在循环里反复调用
find两次——先存结果再比较，避免冗余查找 - 注意图不连通时，循环结束但
edges_used ，此时应返回错误或特殊值（如 -1） - 权值累加用
long long更安全，尤其边权较大或边数多时
long long kruskal(int n, vector& edges) { sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a.w < b.w; }); UnionFind uf(n); long long total = 0; int edges_used = 0; for (auto& e : edges) { int ru = uf.find(e.u), rv = uf.find(e.v); if (ru != rv) { uf.unite(ru, rv); total += e.w; if (++edges_used == n - 1) break; } } return edges_used == n - 1 ? total : -1; }
常见错误：节点编号越界、并查集未初始化、边权类型不匹配
这些不是逻辑问题，而是上线就崩的硬伤。
立即学习“C++免费学习笔记（深入）”；
- 输入节点编号是 1-indexed（比如题目说 “1 到 n”），但你开了
UnionFind(n)却用uf.find(e.u)直接传入——若e.u == n，下标就是n，越界！应开n+1或统一转 0-indexed -
UnionFind构造时忘了iota或循环初始化parent，导致所有find返回随机值 - 边权是
int，但总和存进int total，溢出后变成负数，还误以为图不连通 - 排序时用了
a.w ，破坏严格弱序，std::sort行为未定义
真正卡住人的往往不是算法思想，而是初始化范围、数据类型、索引偏移这三处——每次写完先盯这三行。
