因为kruskal需高效判断加边是否成环，即检查两顶点是否在同一连通分量；并查集通过路径压缩与按秩合并使find/union均摊接近o(α(n))，总复杂度稳定在o(e log e)，而dfs/bfs判环会使时间退化至o(e·v)。
为什么Kruskal要用并查集？
因为Kruskal的核心逻辑是「按边权从小到大选边，跳过会形成环的边」——而判断加一条边是否成环，本质就是判断该边两个端点是否已在同一连通分量中。并查集（union-find）正是为此场景设计的数据结构：支持快速合并（union）和查询（find），平均时间复杂度接近 O(α(n))，远优于每次DFS/BFS判环。
常见错误是手写DFS判环：边排序后逐条尝试加入，再对当前图跑一次连通性检查——这会让整体复杂度退化到 O(E·(V+E))，面对几千条边就明显卡顿。
怎么写一个靠谱的并查集？
重点不在“能跑”，而在「路径压缩 + 按秩合并」必须同时启用，否则最坏情况退化成链表，find 可能 O(V)。别用 vector
-
parent[i] = i初始化不能省，下标从 0 还是 1 开始要和顶点编号对齐 - 合并时比较
rank[root_a]和rank[root_b]，小树挂大树；相等时才给大树 rank+1 -
find必须递归写法或显式栈实现路径压缩，写成 while 循环但没改 parent 指针等于白搭
示例关键片段：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
struct UnionFind {
vector<int> parent, rank;
UnionFind(int n) : parent(n), rank(n, 0) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (x != parent[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]
<h3>边怎么存、怎么排序才不出错？</h3>
<p>Kruskal 的输入是边列表，不是邻接表。别把图读成 <code>vector<vector>></vector></code> 再转边——多此一举还易索引错。直接存三元组：<code>{weight, u, v}</code>，用 <code>sort()</code> 默认按第一项升序排即可。</p>
<ul>
<li>顶点编号若从 1 开始，边里 <code>u</code> 和 <code>v</code> 别忘了 -1（进并查集前）</li>
<li>权重类型统一用 <code>int</code> 或 <code>long long</code>，混用 <code>double</code> 可能因精度导致排序错位</li>
<li>重边不用提前去重：Kruskal 本身会跳过成环边，重复边自然被忽略；但若含负权边，算法仍正确（MST 允许负权）</li>
</ul>
<h3>什么时候停？生成树边数一定是 V-1</h3>
<p>别循环遍历所有边完才结束。一旦收集到 <code>V-1</code> 条边，立刻 break。否则后续边全被跳过，纯属浪费 CPU。</p>
<p>容易忽略的边界：图不连通时，循环结束但边数 <code>，此时应返回空或报错（如抛异常或返回 <code>-1</code> 表示无解）。实际工程中，这个判断比算法主干更重要——否则用户拿到部分结果还以为成功了。</code></p>
<p>最后提醒：Kruskal 对稀疏图友好（E ≈ V），但边数上百万时，<code>sort</code> 成为瓶颈，这时该考虑 Prim + 堆优化。不过95%的 OJ 题和教学场景，Kruskal 更直观、更不易写错。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
