用并查集判断加边是否成环：初始化各点独立，对边(u,v)先find(u)和find(v)，若结果相同则已连通、会成环；find须路径压缩，union推荐按秩合并。
怎么用并查集判断边是否成环
Kruskal 的核心是按权值从小到大加边，但每加一条边前必须确认它不会和已有边构成环。直接遍历图找环太慢，而并查集（Union-Find）刚好能以接近 O(α(n)) 的均摊代价回答「两个顶点是否已在同一连通分量」——也就是「加这条边会不会成环」。
实操要点：
- 初始化时每个顶点自成一个集合，
parent[i] = i - 对每条边
(u, v)，先find(u)和find(v)；如果结果相同，说明已连通，跳过 -
find必须带路径压缩（否则退化成链表，find可能O(n)） -
union推荐按秩合并（或按大小合并），避免树退化；不合并也行，但大数据下性能明显下降
边怎么排序才不影响正确性
Kruskal 依赖严格按边权升序处理，但 C++ 中 std::sort 默认不保证稳定，如果多条边权值相同，它们的相对顺序不确定——而这对结果无影响，只要所有同权边都放在相邻位置即可。
常见错误现象：sort(edges.begin(), edges.end()) 直接对 vector<tuple>></tuple> 排序可能因字段顺序出错。
立即学习“C++免费学习笔记（深入）”；
安全写法：
- 用
vector<array>></array>或自定义结构体，重载operator，确保先比权重，再比端点（可选，仅用于调试一致性） - 或传 lambda：
sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) { return get(a) (b); });（假设权重在第 0 位） - 别把权重存在
double里再排序——浮点误差可能导致顺序错乱；整数权值优先
为什么 Kruskal 在稀疏图上比 Prim 更合适
时间复杂度决定适用场景：O(E log E) 主要来自排序，而并查集操作总和几乎是线性的。当边数 E 远小于顶点数平方（即 E ≈ O(V)），这个复杂度比 Prim 的二叉堆实现 O(E log V) 更友好，更不用说斐波那契堆的常数开销了。
实操中要注意：
- 如果图是稠密的（比如邻接矩阵存的完整图），边数
E = V²，此时log E ≈ 2 log V，和 Prim 差不多，但排序+并查集的 cache 友好性通常仍略胜一筹 - 输入边本身已排序？跳过
sort，直接O(E α(V))，这是真实项目里值得检查的优化点 - 并查集数组大小必须覆盖所有顶点编号——若顶点编号从 1 开始，别只开
parent[n]，得开parent[n+1]，否则访问parent[n]越界
构造最小生成树时怎么保存结果边
算法过程不维护生成树结构，只累计选中的边。最直接的方式是用 vector<array>></array> 或 vector<tuple>></tuple> 存每条被接受的边（u, v, weight）。
容易踩的坑：
- 没在
union(u,v)成功后才 push_back——导致把成环的边也加进去了 - 边的端点顺序随意存，后续建图或输出时搞反方向，虽不影响权值，但调试时容易误判连通性
- 忘了检查最终边数是否等于
V-1：如果不够，说明图不连通，应返回空或报错；这点常被忽略，尤其测试用例含孤立点时
最后提一句：并查集的 find 函数里，parent[x] = find(parent[x]) 这句压缩不能少，否则极端数据下会 TLE——不是理论问题，是实际卡点。
