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）。
容易踩的坑：
- 用
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 <h3>C++ 实现中 union-find 的边界细节</h3>
<p>节点编号常从 0 或 1 开始，但并查集数组下标必须覆盖全部可能节点。若图有 <code>V</code> 个节点，编号为 <code>0..V-1</code>，则并查集数组大小至少为 <code>V</code>；若编号是 <code>1..N</code>，就开 <code>N+1</code> 避免越界。</p>
<p>另一个易忽略点：<code>merge()</code> 返回布尔值表示是否真正合并成功（即两节点原属不同集合），这个返回值可直接用于控制 MST 边收集逻辑，比重复调用 <code>find</code> 更高效。</p>
<p>实操建议：</p>
<ul>
<li>不要用 <code>std::vector<int> parent</int></code> 后再裸用 <code>parent[i]</code>，封装成 <code>find(i)</code> 方法，防止漏路径压缩</li>
<li>如果图不连通，最终 <code>mst_edges.size() != V - 1</code>，此时应报错或返回空结果，而不是强行输出部分树</li>
<li>权值类型用 <code>long long</code> 更安全，尤其当边权可能累加溢出时（虽然 MST 本身不求和，但调试时打印总权值常用）</li>
</ul>
<h3>完整流程中哪些变量必须初始化？</h3>
<p>Kruskal 不是“跑一遍就能出结果”的黑盒，几个关键状态变量一旦未清零或未重置，会在多组测试或重复调用时出错。</p>
<p>必须显式初始化的包括：</p>
<ul>
<li>并查集的 <code>parent</code> 数组：每个 <code>i</code> 对应 <code>parent[i] = i</code>
</li>
<li>并查集的秩/大小数组：全为 0（按秩合并）或全为 1（按大小合并）</li>
<li>MST 边容器（如 <code>vector<edge> mst_edges</edge></code>）：每次新图前要 <code>.clear()</code>
</li>
<li>输入边容器：不能复用上一轮未清空的 <code>edges</code>
</li>
</ul>
<p>最容易被忽略的是——在读入新图前，忘了重置并查集。例如写成全局 <code>Dsu dsu;</code>，然后循环处理多组数据，却不调用 <code>dsu.init(n)</code>，就会沿用上一轮的连通状态，导致结果完全错误。</p></edge>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
