prim算法用priority_queue实现时易出错，因c++优先队列不支持降键操作，需在出队时用inmst[]检查是否已加入mst，避免重复处理；队列应存{weight, node}并用greater实现小根堆；起点入队{0,start}，其余点由松弛过程加入。
Prim 算法用 priority_queue 实现时，为什么老是多加边或漏加点？
Prim 的核心是维护「已连通集合」和「待选边」，但 C++ 的 priority_queue 默认不支持修改堆内元素优先级，所以不能像伪代码里那样“更新邻接点权重”。一旦某个点被加入 MST 后又被更小权边再次推入队列，就会重复处理。
- 必须在出队时检查该点是否已在 MST 中——用布尔数组
inMST[]标记，出队后立刻判断，不是一进队就标记 -
priority_queue要存{weight, node}，且按 weight 升序；C++ 默认大根堆，得用greater或自定义比较 - 图要用邻接表（
vector<vector int>>></vector>），别用邻接矩阵，稀疏图下空间和时间都吃不消 - 起点初始化：把起点的
{0, start}推入，其他点先不入队，靠松弛过程自然加入
Kruskal 需要排序边，sort() 传什么比较函数才不会崩？
边结构体如果只重载 operator，容易因成员未初始化或比较逻辑错位导致 <code>sort 行为未定义（尤其在含负权边或自环时）。最稳的方式是用 lambda 显式比权重。
- 边建议定义为
struct Edge { int u, v, w; };，别用 tuple，可读性和调试成本低得多 sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w —— 必须用 <code>a.w ，不是 <code>，否则可能违反 strict weak ordering- 排序前确保
edges不含自环（u == v）和重复边，Kruskal 对这些没做防御 - 如果图不连通，Kruskal 结束后 MST 边数会小于
n-1，得手动检查，不能默认成功
并查集写 unionSet() 时路径压缩和按秩合并哪个更重要？
两者都重要，但路径压缩（find() 里改父节点）是必须的；按秩合并（unionSet() 里比 rank[]）能进一步压平树高，但漏掉它顶多让单次操作退化到 O(log n)，而没路径压缩可能直接 O(n)。
-
find(x)必须写成递归或带循环+赋值的形式：parent[x] = find(parent[x]);，不能只返回find(parent[x]) -
rank[]初始全 0，合并时只在两棵树 rank 相等时才给新根 rank+1；别用 size 合并（除非你真需要 size 信息） - 注意数组索引：节点编号从 0 还是 1 开始？
parent数组大小得是n+1或n，错一位就访问越界 - 并查集对象别放在函数栈里传值复制，用引用或全局静态，否则每次调用都是新实例
两种算法选哪个？看图密度还是看数据范围？
看边数 m 和点数 n 的比值，不是看“稠密”“稀疏”的模糊描述。实际编码中，m 基本算稀疏，<code>m > n²/4 才值得怀疑是否真需要 Prim。
立即学习“C++免费学习笔记（深入）”；
- Kruskal 时间复杂度 O(m log m)，适合
m ≤ 1e5；超过这量级，排序本身成瓶颈，且常数大 - Prim +
priority_queue是 O(m log n)，但隐式建堆开销明显；若用斐波那契堆理论更优，但 C++ 没原生实现，别折腾 - 如果题目强制要求“从某点开始构造”，或者边权动态变化（虽少见），Prim 更自然；Kruskal 天然无起点概念
- 内存敏感场景（嵌入式、OJ 内存限制严），Kruskal 只需存边和并查集，比 Prim 的邻接表 + 堆省空间
边界情况比教科书写的多：重边要留最小那条、自环直接扔、不连通图得提前判，这些地方一漏，输出就不是最小生成树，而是某棵生成树。
