克鲁斯卡尔算法需边排序+并查集判环：用std::sort按权值（及次级键）升序排序边，配合路径压缩+按秩合并的并查集检测环；边数不足v-1时图不连通，应返回空。
克鲁斯卡尔算法的核心是边排序 + 并查集判环
直接说结论：不用自己手写快排，std::sort 配合自定义比较函数就足够；但必须用并查集（Disjoint Set Union）判断加入某条边是否成环，否则时间复杂度退化到 O(E²)。常见错误是把“按权值排序”当成全部逻辑，漏掉环检测——结果生成的不是树，而是带环图或森林。
典型使用场景：稀疏图（E ≈ V）、边已显式给出（如输入就是边列表）、需要输出最小生成树的边集而非仅权值和。
-
std::vector<:tuple int>></:tuple>存边：(weight, u, v)，方便用std::sort默认升序 - 并查集必须路径压缩 + 按秩合并，否则最坏查询接近
O(log V)，整体变慢 - 边数少于
V-1时直接返回空，图不连通，不存在最小生成树
怎么写一个高效的并查集辅助克鲁斯卡尔
别用 map 或 set 实现 parent，用 std::vector<int></int> 下标即节点编号（假设节点编号为 0 到 V-1）。初始化时 parent[i] = i，rank[i] = 0。
关键点在于 find 必须带路径压缩，unionSets 必须按秩合并——否则在稠密测试用例（如 1e5 条边）下会 TLE 或 WA。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
-
find(x)返回根，并把沿途所有节点父指针直接连到根 -
unionSets(x, y)只在两根不同时才合并，且小树挂到大树下（用rank判断） - 返回
true表示成功合并（即无环），false表示已连通（加这条边会成环）
std::sort 边时容易踩的坑
错误写法：sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return get(a) (b); }); 看似没问题，但若权值相同，后续行为不可控——不同 STL 实现可能打乱原始顺序，导致本该选的边被跳过。
更稳妥的做法是三元组排序时加次级键（比如节点编号），保证稳定：
sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
if (get(a) != get(b)) return get(a) (b);
if (get(a) != get(b)) return get(a) (b);
return get(a) (b);
});
- 不加次级键不影响正确性，但影响可复现性（尤其调试时）
- 如果输入边本身已按权值有序，仍建议调用
sort——别依赖输入顺序 - 避免用
float或double作权值参与比较，浮点误差可能让相等权值被误判大小
完整流程中常被忽略的边界检查
很多人写完核心循环就交，但实际运行时崩溃或输出错误，往往卡在这些地方：
- 节点编号是否从
0开始？若输入是1-indexed，记得建并查集时 size 设为V+1，且所有u,v减1 - 输入含重边？克鲁斯卡尔本身能处理，但若手动去重反而可能删掉权值小的那条，应保留所有边让
sort自行选择 - 权值为负？算法支持，但需确认题意是否允许（负权边在 MST 中合法，不影响 Kruskal 正确性）
- 最后生成的边数不是
V-1？说明图不连通，此时应返回空集或报错，而不是强行凑满
最麻烦的是节点编号稀疏（比如只有 1、100、10000），但你按最大编号分配了 1e5 大小的 parent 数组——内存浪费且易越界。真遇到这种，先离散化节点编号再做并查集。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
