必须用std::sort按边权升序排序后再跑kruskal；推荐用struct edge封装并自定义lambda比较器；并查集需路径压缩+按秩合并；判断连通性前须检查节点范围并先存find结果；mst边需实时存储而非仅计数。
怎么用 std::sort 对边排序再跑 Kruskal
Kruskal 的核心是按边权从小到大处理，所以必须先排序。别手写快排，直接用 std::sort 最稳。
常见错误：把边存成 vector<pair pair int>>></pair> 后只按第一维排序，结果 pair 默认比较规则会连带比较节点编号，导致顺序错乱。
- 推荐结构体封装：
struct Edge { int u, v, w; };，然后自定义 lambda：sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w - 如果用
tuple<int></int>，务必用get(e)显式取权重，避免隐式比较陷阱 - 注意：排序前确保所有边的
w已赋值，否则未初始化值参与比较会触发 UB
并查集 find 和 unionSet 怎么写才不 TLE
朴素并查集在稠密图里容易退化成 O(n) 每次查询，Kruskal 整体就变 O(mn)，1e5 边直接超时。
必须路径压缩 + 按秩合并。别省那几行代码。
立即学习“C++免费学习笔记（深入）”；
-
find一定要递归写法或显式循环压栈，返回时更新parent[x] = find(parent[x])；写成 while 循环但忘了改父指针，等于白压 -
unionSet中比较秩（rank[u]vsrank[v]），小树挂大树；相等时才给根节点秩+1，漏掉这个条件会导致后续树高失控 - 数组大小别开小了——节点编号从 1 开始？那
parent[1..n]至少要声明为vector<int>(n+1)</int>，下标 0 别乱用
什么时候该跳过一条边：判断连通性的正确姿势
不是看到 find(u) == find(v) 就直接 continue，得确认这俩是不是真在一个集合里——而这是 find 返回根的结果，不是原始编号。
典型翻车点：调用 find 前没保证参数在合法范围内，比如读入边时 u 或 v 超出 [1,n]，find 数组越界访问后行为不可预测。
- 加一句断言或调试输出：
assert(u >= 1 && u = 1 && v - 合并前先
int ru = find(u), rv = find(v); if (ru == rv) continue;，别把find(u) == find(v)写进 if 条件里还重复调用两次 - 注意无向图每条边只处理一次，别因为输入含重边或自环，导致同一条边被反复判连通
构建 MST 边集时为什么不能只计数、还得存具体边
题目只要最小生成树权值和？那累加就行。但一旦要输出选了哪些边、或者需要重构树结构（比如后续 DFS），只记总数会丢信息。
更隐蔽的问题：有些题数据保证有解，但实际输入可能不连通——这时 Kruskal 结束后选中的边数 ，必须检查，否则输出错误答案。
- 用
vector<edge> mstEdges;</edge>实时 push，比单独维护sum和cnt更可靠 - 循环结束后立刻判断：
if (mstEdges.size() != n - 1) { /* 图不连通 */ }，别等到输出时才发现 - 如果题目要求输出字典序最小的 MST，那排序时要在权重相等的前提下，按
min(u,v)、max(u,v)稳定排序，否则相同权边顺序不定
边排序的稳定性、并查集的压缩时机、连通性判断前的边界检查——这三个地方出错，调试时往往看不出逻辑问题，只能靠打印中间状态才能定位。
