克鲁斯卡尔算法的核心是并查集而非排序，本质为贪心：按边权升序选边，用带路径压缩和按秩合并的并查集判断并避免成环，边数达V-1时终止，需验证连通性。
克鲁斯卡尔算法的核心是并查集，不是排序本身
克鲁斯卡尔本质是贪心：按边权从小到大选边，只要不形成环就加入 MST。判断“是否成环”靠并查集（Union-Find），不是靠 DFS 或 visited 数组——后者在动态加边时无法高效维护连通性。
常见错误是只做排序，漏掉并查集合并逻辑，导致重复连通、生成环或遗漏边。实际运行中，find 和 union 的实现必须带路径压缩和按秩合并，否则最坏情况退化到 O(E×V)。
-
find必须递归或迭代压缩路径，避免链式查找 -
union优先把小树挂到大树下（用rank或size数组记录） - 边数组建议用
std::vector<std::tuple<int, int, int>>存储（权重, u, v），方便std::sort
边排序后必须逐条检查连通性，不能跳过已处理节点
排序完直接遍历，对每条边 (w, u, v) 先 find(u) != find(v) 再 union(u, v) 并计入 MST。这里容易错在：把 u 和 v 当作数组下标直接访问父节点，而没调用 find——并查集的根节点可能未更新，导致误判连通。
示例片段（关键逻辑）：
立即学习“C++免费学习笔记（深入）”；
for (auto [w, u, v] : edges) {
int ru = find(u), rv = find(v);
if (ru != rv) {
mst_edges.push_back({u, v, w});
union_sets(ru, rv); // 注意传 root，不是 u/v
total_weight += w;
}
}
- 务必对
u和v分别调用find获取当前根，再比较 -
union_sets参数应为两个根节点，不是原始顶点编号 - 边数达到
V-1可提前退出，但需确保图连通；否则最后要检查mst_edges.size() == V-1
C++ 实现中 vector 下标和顶点编号易混淆
顶点编号常从 0 或 1 开始，而并查集数组（如 parent）大小必须覆盖所有可能顶点号。若输入顶点是 1~n，parent 长度至少为 n+1，且初始化 parent[i] = i 要覆盖全部有效编号。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
典型坑点：
- 读入边时把
u、v当作 0-based 处理，但图中实际是 1-based，导致越界或错连 -
parent数组只开n长度，访问parent[n]时越界（当顶点含 n） - 没初始化所有顶点的
parent[i]，残留垃圾值造成find返回非法地址
稳妥做法：parent.resize(n + 1); iota(parent.begin(), parent.end(), 0);
边权为负数或存在重边时需额外处理
克鲁斯卡尔本身支持负权边（最小生成树定义不限制权正负），但重边（多条 u-v 边）必须保留所有候选边参与排序——不能去重，否则可能丢掉更优边。例如 u-v 有两条边：权 -5 和 3，取 -5 才对。
另外，若图不连通，算法会自然停在 V-1 条边之前，此时 mst_edges.size() < V-1，应返回无解。不要强行补边或忽略该检查。
- 输入阶段就用
vector<tuple<int,int,int>>存所有边，不做 dedup - 排序用
sort(edges.begin(), edges.end())即可（tuple默认按第一项升序） - 结束后必须验证连通性：
if (mst_edges.size() != n - 1) { /* not connected */ }
真正麻烦的是稀疏图里大量孤立点——它们在并查集中始终自成一类，但不会出现在任何边里，所以初始化时仍要为每个点设 parent[i]=i，哪怕它没在边列表中出现过。
