kruskal算法必须使用带路径压缩和按秩合并的并查集，因其是唯一能高效判断连通性与动态合并连通分量的基础设施；裸并查集在边数达10⁵时易tle或wa。
直接说结论： Kruskal 算法必须配合并查集（Union-Find）才能高效判断环、合并连通分量；不带路径压缩和按秩合并的裸 find/union 在稀疏图上可能 TLE 或 WA，尤其边数接近 10⁵ 时。
为什么非得用并查集？——不是“能用”，是“绕不开”
Kruskal 的核心逻辑是：从小到大取边，只加“连接两个不同连通块”的边。问题来了——怎么快速知道两个顶点 u 和 v 是否已连通？
- 暴力 DFS/BFS 每次判连通：O(V+E) × 边数 → 肯定超时
- 邻接矩阵维护连通性：O(V²) 空间 + 每次合并要刷整行/列 → 不现实
- 并查集：单次
find平均 O(α(V))，union同样极快，且天然支持动态合并
换句话说，并查集不是“辅助工具”，它是 Kruskal 正确性和效率的基础设施。
关键函数怎么写？——find 必须带路径压缩，unionSet 建议加按秩合并
常见错误是写一个只递归不压缩的 find，导致深度退化成链表，最坏 O(n)；或者 union 盲目挂树，让树越来越高。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
-
find(x)：用循环或递归找到根，**同时把路径上所有节点父指针直连根**（路径压缩） -
unionSet(u, v)：先find(u)和find(v)，若根不同才合并；推荐用rank数组控制谁挂谁（小树挂大树），避免深度暴涨 - 初始化：
father[i] = i，rank[i] = 0（或全 1，看实现习惯）
示例片段（C++）：
int find(int x) {
return father[x] == x ? x : father[x] = find(father[x]); // 递归+路径压缩
}
void unionSet(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (rank[u] <h3>边排序和主循环怎么组织？——别漏判“无法生成树”的情况</h3><p>排序本身简单，但要注意两点：一是结构体数组 + <code>sort</code> 或 <code>qsort</code>；二是主循环里必须统计加入的边数，不能只靠遍历完所有边就结束。</p>
- 边存为结构体：
struct Edge { int u, v, w; };，重载operator 或写 <code>cmp函数 - 主循环终止条件是
edges_used == n - 1，不是i ；提前 break 更安全 - 循环结束后检查：
if (edges_used != n - 1) return -1;（说明图不连通，无 MST） - 权值累加放在
unionSet成功后，别放错位置
容易被忽略的细节：索引从 0 还是 1 开始？rank 初始值填多少？
这直接导致越界或逻辑错误，但很多人调试半天才发现。
- 如果顶点编号是 1～n，
father和rank数组大小至少为n+1，下标 0 不用也得留空 -
rank初始全 0 是标准做法（表示单节点树高度为 0）；填 1 也可以，但union逻辑要同步改，否则rank[u] == rank[v]判断失效 - 输入边时注意方向无关性：无向图中
(u,v)和(v,u)等价，但并查集不关心方向，只要两端点正确即可 - 边权为 0 或负数？Kruskal 仍适用，排序和比较逻辑不变
真正卡住人的往往不是算法思想，而是 father 数组开小了、find 忘了赋值、或者 unionSet 里没先 find 就直接操作原节点。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
