prim算法应使用std::set替代priority_queue以支持权值更新，配合inmst[]数组判重；kruskal需路径压缩与按秩合并，并注意输入索引偏移、重边处理及数据类型溢出。
Prim 算法怎么写才不爆内存又不出错
Prim 的核心是用优先队列维护「当前已连通集合到未访问点的最短边」，但 C++ 里直接套 std::priority_queue 容易翻车——它不支持修改已有元素的权值，导致重复入队、判重逻辑混乱。
常见错误现象：std::priority_queue 里塞了多个相同顶点的不同权重，却只靠顶点编号判重，结果跳过更优路径；或者手动清空队列时漏掉中间状态，生成树边数不对。
- 用
std::set<:pair int>></:pair>替代堆：第一个int是权值（升序），第二个是顶点编号；插入前先erase掉旧记录，再insert新记录，天然去重+可更新 - 必须维护一个
inMST[]布尔数组，每次从set取出最小边时，先检查对应顶点是否已在 MST 中，否则直接continue - 邻接表存图时，边权类型别用
int硬扛大数值，推荐long long，尤其题目没说权值范围时
Kruskal 算法为什么排序后 union-find 还连不上
Kruskal 正确性的前提是：边按权值升序处理，且每次合并两个不同连通分量。但实际写的时候，find 函数没路径压缩、union 没按秩合并，小图看不出问题，一到稀疏图或大数据就超时或误判连通性。
使用场景：适合边少、点多的图（比如地理坐标建模），比 Prim 更容易并行化，但对边排序开销敏感。
立即学习“C++免费学习笔记（深入）”；
-
find必须带路径压缩：parent[x] = find(parent[x])，否则多次查询退化成链表遍历 -
union时比较的是根节点的秩（rank[root_a]），不是原节点；合并后记得更新秩：if (rank[a] == rank[b]) rank[a]++ - 输入边数组别用
vector<tuple>></tuple>然后sort，改用vector<array>></array>或自定义结构体 + 重载operator，避免 tuple 构造开销
Prim 和 Kruskal 在稠密图上性能差在哪
Prim 用邻接矩阵实现时时间复杂度是 O(V²)，看着稳，但实际 V=1e4 就要跑 1e8 次循环，C++ 都可能 TLE；Kruskal 对于完全图（E ≈ V²）要排序 V² 条边，std::sort 均摊 O(E log E) ≈ 1e8 × log₂(1e8) ≈ 2.7e9 次操作，远超 1 秒限制。
性能影响关键点不在算法本身，而在数据结构选择和常数控制：
- 稠密图（E > V log V）优先用 Prim + 邻接表 +
set（实际常数比堆小），而不是死守邻接矩阵 - Kruskal 处理超大边集前，先用
reserve()预分配 vector 容量，避免多次 realloc - 读入边时别用
cin >> u >> v >> w，关同步：ios::sync_with_stdio(false); cin.tie(nullptr);
两种算法输出结果不一致？先查这三处
不是算法错了，大概率是图建得不对，或者权值/顶点编号处理有偏差。特别是无向图边只存一次、还是双向都存，会直接影响 Prim 的邻接表遍历范围。
容易踩的坑集中在输入解析和索引偏移：
- 题目给的是 1-indexed 顶点，但代码用 0-indexed 数组存，忘了把输入的
u和v减 1 —— Kruskal 的边排序没问题，但 union-find 合并了错误下标 - Prim 初始化时，把起点的权值设为 0 没问题，但没把起点的
inMST[0] = true，导致它又被重新加入候选集 - 图含重边时，Kruskal 要么提前去重（保留最小权值那条），要么确保排序稳定（相同权值边按端点大小再排），否则不同编译器下
std::sort行为可能微异
最小生成树不唯一时，两种算法给出不同边集完全正常；但总权值必须相等。如果总权值不等，一定是某处越界访问、整数溢出，或 union-find 的根没找对。
