因为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++免费学习笔记（深入）”；
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] < rank[y]) swap(x, y);
parent[y] = x;
if (rank[x] == rank[y]) rank[x]++;
}
};
边怎么存、怎么排序才不出错？
Kruskal 的输入是边列表，不是邻接表。别把图读成 vector<vector<pair<int,int>> 再转边——多此一举还易索引错。直接存三元组：{weight, u, v}，用 sort() 默认按第一项升序排即可。
- 顶点编号若从 1 开始，边里
u和v别忘了 -1（进并查集前） - 权重类型统一用
int或long long，混用double可能因精度导致排序错位 - 重边不用提前去重：Kruskal 本身会跳过成环边，重复边自然被忽略；但若含负权边，算法仍正确（MST 允许负权）
什么时候停？生成树边数一定是 V-1
别循环遍历所有边完才结束。一旦收集到 V-1 条边，立刻 break。否则后续边全被跳过，纯属浪费 CPU。
容易忽略的边界：图不连通时，循环结束但边数 < V-1，此时应返回空或报错（如抛异常或返回 -1 表示无解）。实际工程中，这个判断比算法主干更重要——否则用户拿到部分结果还以为成功了。
最后提醒：Kruskal 对稀疏图友好（E ≈ V），但边数上百万时，sort 成为瓶颈，这时该考虑 Prim + 堆优化。不过95%的 OJ 题和教学场景，Kruskal 更直观、更不易写错。
