Kruskal算法必须用并查集，因其需高效判断加边是否成环，即判断u、v是否在同一连通分量；不用并查集而用BFS/DFS会使时间退化为O(E·V)，而并查集配合路径压缩与按秩合并可将总复杂度稳定在O(E log E)。
为什么 Kruskal 算法必须用并查集？
因为 Kruskal 的核心逻辑是「按边权从小到大加边，跳过会成环的边」——而判断加某条边 (u, v) 是否成环，等价于判断 u 和 v 是否已在同一连通分量中。不用并查集，就得每次做 BFS/DFS 检测连通性，时间直接退化到 O(E·V)；用带路径压缩和按秩合并的并查集，单次 find 和 union 均摊接近 O(α(V))，总复杂度稳在 O(E log E)。
常见错误：手写一个朴素数组标记连通块（比如用 comp_id[v]），但没实现动态合并逻辑，导致后续边的连通性判断失效。
实操建议：
- 并查集结构体里务必封装
find()（带路径压缩）和merge()（带按秩/大小合并） - 初始化时每个节点的父节点设为自己，秩/大小数组全为 1 或 0
- 合并前先
find(u)和find(v)，只对根节点操作
如何正确排序边并避免重复加边？
输入边通常是无序的，且可能含重边或自环。Kruskal 对边的处理顺序极为敏感：必须严格按权重升序，权重相同时顺序不影响正确性，但影响生成树形态（不过仍是合法 MST）。
立即学习“C++免费学习笔记（深入）”；
容易踩的坑：
- 用
std::sort时传错比较函数，比如写成a.weight > b.weight导致降序 - 忘记过滤自环（
u == v），这种边永远不能加入 MST - 多条相同权值的边中，某条边的两个端点已在同一集合，却仍把它计入 MST 边数统计
示例关键片段：
struct Edge { int u, v, w; };
vector<Edge> edges;
// ... 输入后
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.w < b.w; // 严格升序
});
for (auto& e : edges) {
if (e.u == e.v) continue; // 跳过自环
if (dsu.find(e.u) != dsu.find(e.v)) {
dsu.merge(e.u, e.v);
mst_edges.push_back(e); // 只在这儿加
}
}C++ 实现中 union-find 的边界细节
节点编号常从 0 或 1 开始，但并查集数组下标必须覆盖全部可能节点。若图有 V 个节点，编号为 0..V-1，则并查集数组大小至少为 V；若编号是 1..N，就开 N+1 避免越界。
另一个易忽略点：merge() 返回布尔值表示是否真正合并成功（即两节点原属不同集合），这个返回值可直接用于控制 MST 边收集逻辑，比重复调用 find 更高效。
实操建议：
- 不要用
std::vector<int> parent后再裸用parent[i]，封装成find(i)方法，防止漏路径压缩 - 如果图不连通，最终
mst_edges.size() != V - 1，此时应报错或返回空结果，而不是强行输出部分树 - 权值类型用
long long更安全，尤其当边权可能累加溢出时（虽然 MST 本身不求和，但调试时打印总权值常用）
完整流程中哪些变量必须初始化？
Kruskal 不是“跑一遍就能出结果”的黑盒，几个关键状态变量一旦未清零或未重置，会在多组测试或重复调用时出错。
必须显式初始化的包括：
- 并查集的
parent数组：每个i对应parent[i] = i - 并查集的秩/大小数组：全为 0（按秩合并）或全为 1（按大小合并）
- MST 边容器（如
vector<Edge> mst_edges）：每次新图前要.clear() - 输入边容器：不能复用上一轮未清空的
edges
最容易被忽略的是——在读入新图前，忘了重置并查集。例如写成全局 Dsu dsu;，然后循环处理多组数据，却不调用 dsu.init(n)，就会沿用上一轮的连通状态，导致结果完全错误。
