最小生成树（MST）的定义是？
考点：最小生成树的定义（A1）。
解析：MST = 连通无向图中连接所有 个点的 条边组成的边权和最小的树。✅ 正确
排除法：B 是最短路子图；C 只要求连通不要求权最小；D 是路径不是树。
关联 · A2 生成树性质：树 = 连通 + 无环。
判断题： 个点的生成树恰有 条边，且连通、无环。
考点：生成树性质（A2）。
解析： 个点的生成树恰有 条边，且连通、无环——三性质互相等价（满足其二即为其三）。✅ 正确
排除法：无（判断题）。混淆点： 条边是"恰好"，不是"至少"。
关联 · L4 填空：Kruskal 取满 条即停。
判断题：最小生成树在任何情况下都一定唯一。
考点：MST 唯一性（A3）。
解析：MST 不一定唯一——边权互异时才唯一；有相等边权时可能存在多棵代价相同的 MST。"任何情况下都唯一"是错的。✅ 答案 B（错误）
排除法：无（判断题）。混淆点：唯一的是最小代价这个值，树本身可以多棵。
关联 · E5 MST 变体：多解是边权相等的自然产物。
MST 的典型应用是？
考点：MST 的应用（A4）。
解析：布线/连通城市的最小总代价等"全局最小连通"问题——MST 是这类问题的标准模型。✅ 正确
排除法：B 是最短路；C/D 无关。
关联 · E1 布线问题：原型问题。
判断题：MST 保证的是全局连通代价最小；它不保证任意两点之间的路径是该两点的最短路。
考点：与最短路区别（A5）。
解析：MST 保证全局连通代价最小；不保证任意两点间路径是该两点最短路。✅ 正确
排除法：无（判断题）。混淆点：目标不同——一个是全局、一个是两点。
关联 · N4 代码：同图 MST=5、dist[4]=5 只是巧合。
MST 两算法总表是？
考点：算法总表（A6）。
解析：Prim 从点扩展（朴素 、堆优化 ）；Kruskal 从边排序（）。✅ 正确
排除法：B/C 复杂度荒谬；D 反了（Prim 适合稠密）。
关联 · G1 总表：两法 + 拓扑的总表。
Prim 的核心思想是？
考点：Prim 的思想（B1）。
解析：从一个点出发，每次把"离已选点集合最近"的点加入，直到 个点全加入——像 Dijkstra 的"点扩展"。✅ 正确
排除法：B 是 Kruskal；C/D 无依据。
关联 · B5 割性质：贪心正确性来源。
Prim 的步骤是？
考点：Prim 的步骤（B2）。
解析：初始化 → 循环 次：选未在树中 最小的点 加入 → 用 的出边更新邻居的 。✅ 正确
排除法：B 是 Kruskal；C/D 无依据。
关联 · I 组代码：三步循环即朴素版骨架。
朴素 Prim 与堆优化 Prim 的复杂度分别是？
考点：Prim 的复杂度（B3）。
解析：朴素 （每轮线性选点）、堆优化 。✅ 正确
排除法：B/D 错；C 的 是 Kruskal。
关联 · B6 稠密图适用：稠密图朴素版反而优。
Prim 与 Dijkstra 的关键区别是？
考点：与 Dijkstra 对比（B4）。
解析：Dijkstra 的 是"到起点距离"（更新 ）；Prim 的 是"到已选集合的最小边权"（更新 ）。✅ 正确
排除法：B 错——两者转移式不同；C/D 无依据。
关联 · P4 易错：更新式写混会算错代价。
判断题：Prim 每次取跨集合的最小边——贪心正确性来自割性质（任一切割的最小边必在某棵 MST 中）。
考点：割性质（B5）。
解析：Prim 每次取跨集合的最小边——贪心正确性来自割性质（任一切割的最小边必在某棵 MST 中）。✅ 正确
排除法：无（判断题）。混淆点：割 = 已选点集与未选点集之间的边集。
关联 · B1 思想：割性质是证明。
判断题：稠密图（ 接近 ）首选朴素 Prim—— 反优于堆优化版的 。
考点：稠密图适用（B6）。
解析：稠密图（）首选朴素 Prim—— 优于堆优化版的 。✅ 正确
排除法：无（判断题）。混淆点：与 Dijkstra 朴素/堆优化的取舍同理。
关联 · G2 稠密稀疏选择：规模决定版本。
判断题：Prim/Kruskal 只适用于边权非负的图，出现负权边就失效。
考点：负权边（B7）。
解析：Prim/Kruskal 可以处理负权边——求的是最小边权和，负边只会让答案更小，贪心依然正确。"只适用非负权"是错的。✅ 答案 B（错误）
排除法：无（判断题）。混淆点：与 Dijkstra 不同，MST 两算法都不怕负权（怕的是负环，但无向图负环不参与 MST）。
关联 · A4 定义：目标是最小和，与符号无关。
Kruskal 的核心思想是？
考点：Kruskal 的思想（C1）。
解析：按边权从小到大排序，依次取边；两端点未连通的边才加入（并查集判环）。✅ 正确
排除法：B 是 Prim；C/D 无依据。
关联 · C7 必须先排序：排序是贪心前提。
Kruskal 的步骤是？
考点：Kruskal 的步骤（C2）。
解析：边排序 → 初始化 个独立集合 → 遍历边 find 判环、union 合并 → 取满 条停止。✅ 正确
排除法：B/C/D 都不是 Kruskal。
关联 · J 组代码：五步流程。
Kruskal 用并查集判环的方法是？
考点：并查集判环（C3）。
解析：边两端 find 同根则已连通——加边会成环，跳过；不同根才 union。✅ 正确
排除法：B/C 无关；D 错——能判。
关联 · J3 代码：skip 计数即判环实例。
Kruskal 的复杂度是？
考点：Kruskal 的复杂度（C4）。
解析：（排序主导）+ 并查集近乎 。✅ 正确
排除法：B/C/D 全错。
关联 · G2 选择：稀疏图 Kruskal 最优。
判断题：Kruskal 每次选"不构成环的最小边"——贪心正确（环性质：环上最大边不属于 MST）。
考点：正确性（C5）。
解析：Kruskal 每次选"不构成环的最小边"——贪心正确（环性质：环上最大边不属于 MST）。✅ 正确
排除法：无（判断题）。混淆点：环性质与割性质是 MST 贪心的两大支柱。
关联 · B5 割性质：Prim 用割、Kruskal 用环。
判断题：Kruskal 适合稀疏图且依赖并查集；Prim 适合稠密图且长得像 Dijkstra——两者殊途同归。
考点：与 Prim 对比（C6）。
解析：Kruskal 适合稀疏图且依赖并查集；Prim 适合稠密图且长得像 Dijkstra——两者殊途同归。✅ 正确
排除法：无（判断题）。混淆点：结果相同（代价唯一），实现不同。
关联 · G2 选择：按稠密稀疏选。
判断题：Kruskal 必须先按边权升序排序——不排序直接取边，贪心就会失效。
考点：必须先排序（C7）。
解析：Kruskal 必须先按边权升序排序——不排序直接取边，贪心就会失效。✅ 正确
排除法：无（判断题）。混淆点：排序是 的来源。
关联 · P5 排序反：降序得到的是最大生成树。
拓扑排序的前提是？
考点：DAG 前提（D1）。
解析：拓扑排序只对有向无环图（DAG）有定义——有环的图没有拓扑序。✅ 正确
排除法：B/C/D 都不是前提（不要求连通、不适用于无向图）。
关联 · D4 判环：有环 ⟺ 输出不完。
入度的定义是？
考点：入度概念（D2）。
解析：入度 = 指向该点的边数。✅ 正确
排除法：B 是出度；C 是度数（入+出）；D 无关。
关联 · D3 Kahn 步骤：入度 0 的点才能先做。
Kahn（BFS 版）拓扑排序的步骤是？
考点：Kahn 步骤（D3）。
解析：所有入度 0 的点入队 → 出队输出，其出边终点入度减 1，减到 0 再入队 → 直到队空。✅ 正确
排除法：B/C/D 都不是 Kahn。
关联 · K 组代码：BFS 版拓扑。
判断题：Kahn 结束时输出点数 ⟺ 图中有环（环上点的入度永远不为 0）。
考点：判环（D4）。
解析：Kahn 结束时输出点数 ⟺ 图中有环（环上点的入度永远不为 0，永不出队）。✅ 正确
排除法：无（判断题）。混淆点：判环是拓扑排序的免费副产品。
关联 · K4/O7 代码：cnt 与 n 比较。
判断题：DAG 的拓扑序一定唯一。
考点：多解性（D5）。
解析：拓扑序不一定唯一——同一时刻多个入度 0 的点，选谁先输出都合法。"一定唯一"是错的。✅ 答案 B（错误）
排除法：无（判断题）。混淆点：K1 与 K2 就是同一 DAG 的两个合法拓扑序。
关联 · K2 另一种拓扑序：换邻接顺序即换序。
判断题：DFS 版拓扑排序 = 对每个未访问点做 DFS，后序（离开时）压入结果，最后反转；递归栈中遇到回边则判有环。
考点：DFS 思想（D6）。
解析：DFS 版拓扑 = 对每个未访问点 DFS，后序（离开时）压入结果，最后反转；递归栈中遇回边（vis=1 未完成）判有环。✅ 正确
排除法：无（判断题）。混淆点：前序不行——先序输出的不满足依赖。
关联 · N3 代码：后序输出 4 2 3 1，反转才得拓扑序。
拓扑排序的典型应用是？
考点：应用（D7）。
解析：课程先修安排、编译依赖、工程调度等"有依赖关系"的排序——拓扑排序主场。✅ 正确
排除法：B/C 不是拓扑的用途；D 无关。
关联 · F 组拓扑应用：M 组代码全是实例。
判断题：n 个城市用最少的电缆总长连通 = 求 MST——布线是 MST 的经典原型。
考点：布线问题（E1）。
解析：n 个城市用最少的电缆总长连通 = 求 MST——布线是 MST 的经典原型。✅ 正确
排除法：无（判断题）。混淆点：问"总代价"用 MST，问"两点线路"才用最短路。
关联 · A4 应用：原型即应用。
最大生成树的求法是？
考点：最大生成树（E2）。
解析：Kruskal 按边权降序排序（或全部边权取负跑最小生成树）。✅ 正确
排除法：B 求的是最小；C/D 无关。
关联 · L1 代码：降序得 13。
判断题：次小生成树思想——枚举替换 MST 上的一条边，换成不连成环的次优边，取总代价最小者。
考点：次小生成树思想（E3）。
解析：次小生成树 = 枚举替换 MST 上的一条边，换成不连成环的次优边，取总代价最小者。✅ 正确
排除法：无（判断题）。混淆点：S 组进阶考点，暴力枚举 、LCA 优化。
关联 · L3 代码：删边重算实例得 8。
判断题：MST 上两点路径的最大边权 = 这两点间"最小化最大边权"路径（瓶颈路）的最优解。
考点：瓶颈路（E4）。
解析：MST 上两点路径的最大边权 = 这两点间"最小化最大边权"路径（瓶颈路）的最优解。✅ 正确
排除法：无（判断题）。混淆点：MST 不保证最短路，但保证瓶颈路。
关联 · L2 代码：MST 最大边 = 2。
判断题：MST 变体——生成树计数、带重边取最小、边权相等时多解——都以基本两算法为基础扩展。
考点：MST 变体（E5）。
解析：生成树计数、带重边取最小、边权相等时多解——都以基本两算法为基础扩展。✅ 正确
排除法：无（判断题）。混淆点：变体很多，核心思想不变。
关联 · A3 唯一性：多解是变体之一。
判断题：MST（Prim/Kruskal）定义在无向连通图上；有向图的最小树形图是另一个问题。
考点：只用于无向图（E6）。
解析：MST（Prim/Kruskal）定义在无向连通图上；有向图的最小树形图是另一个问题。✅ 正确
排除法：无（判断题）。混淆点：别拿 Kruskal 去求有向图 MST。
关联 · A1 定义：定义域即无向图。
判断题：课程先修关系建模成 DAG——先修课指向后修课，拓扑序就是合法选课顺序。
考点：课程安排（F1）。
解析：课程先修关系建模成 DAG——先修课指向后修课，拓扑序就是合法选课顺序。✅ 正确
排除法：无（判断题）。混淆点：边的方向 = 依赖方向（先→后）。
关联 · M1 代码：输出 1 2 3 4。
判断题：依赖关系成环 = 依赖冲突（如 A 依赖 B、B 依赖 A）——拓扑判环即可检测。
考点：依赖冲突（F2）。
解析：依赖关系成环 = 依赖冲突（A 依赖 B、B 依赖 A）——拓扑判环即可检测。✅ 正确
排除法：无（判断题）。混淆点：判环 = 判"无解"。
关联 · M3 代码：环 → NO。
判断题：DAG 上 DP 按拓扑序做——处理点 时其所有前驱已计算完，转移正确。
考点：DAG 上 DP（F3）。
解析：DAG 上 DP 按拓扑序做——处理点 时其所有前驱已计算完，转移正确。✅ 正确
排除法：无（判断题）。混淆点：拓扑序是 DAG 的"无后效性"保证。
关联 · M2 代码：最长路 DP 实例。
判断题：DAG 上求最长路（AOE 关键路径思想）——把最短路 DP 的 min 换成 max，在拓扑序上做。
考点：关键路径思想（F4）。
解析：DAG 上求最长路（AOE 关键路径思想）——把最短路 DP 的 min 换成 max，在拓扑序上做。✅ 正确
排除法：无（判断题）。混淆点：有环图最长路是 NP 难——必须 DAG。
关联 · M4 填空：
dist[v] = max(dist[v], dist[u]+w)。
字典序最小拓扑序用？
考点：字典序最小拓扑序（F5）。
解析：用优先队列（小根堆）代替普通队列——每次取编号最小的入度 0 点。✅ 正确
排除法：B 普通队列不保证字典序；C 栈是 DFS 版；D 不是拓扑。
关联 · K6/M5 代码：pq 输出 1 2 3 4。
判断题：拓扑排序是"DAG 上的调度语言"——判环、排序、DP 顺序三合一。
考点：应用综合（F6）。
解析：拓扑排序是"DAG 上的调度语言"——判环、排序、DP 顺序三合一。✅ 正确
排除法：无（判断题）。混淆点：三用途记住就够用。
关联 · M 组应用代码：三用途各有一题。
Prim/Kruskal/拓扑排序总表是？
考点：总表（G1）。
解析：Prim 朴素 、Kruskal 、拓扑 Kahn 。✅ 正确
排除法：B/C/D 数值错。
关联 · G2 选择：总表背熟再选。
、 的稠密图求 MST，选？
考点：稠密稀疏选择（G2）。
解析：、 的稠密图求 MST → 朴素 Prim 。✅ 正确
排除法：B 也可但稠密图排序 劣于 ；C/D 用途不同。
关联 · B6 稠密图适用：同结论。
判断题：判环工具选择——无向图用并查集或 DFS；有向图用拓扑排序或 DFS 三色标记。
考点：判环工具选择（G3）。
解析：无向图用并查集或 DFS；有向图用拓扑排序或 DFS 三色标记。✅ 正确
排除法：无（判断题）。混淆点：并查集只能判无向环（有向环找不出）。
关联 · C3/D4：两种判环场景。
"边数很少（稀疏图）+ 求 MST"，选？
考点：场景选择（G4）。
解析：边数很少（稀疏图）+ 求 MST → Kruskal（，并查集判环）。✅ 正确
排除法：B 朴素 Prim 稠密图才优；C/D 用途不同。
关联 · C4 复杂度：稀疏图排序便宜。
判断题：MST 与最短路目标不同——别拿 Dijkstra 求 MST、也别拿 MST 求两点最短路。
考点：与最短路对比（G5）。
解析：MST 与最短路目标不同——别拿 Dijkstra 求 MST、也别拿 MST 求两点最短路。✅ 正确
排除法：无（判断题）。混淆点：两者代码相似（Prim 像 Dijkstra）但语义不同。
关联 · A5 区别：同图同值只是巧合。
判断题：选择流程——求全局连通最小代价用 MST（稠密 Prim/稀疏 Kruskal）；求依赖顺序/判有向环用拓扑；求两点路径用最短路。
考点：选择综合（G6）。
解析：全局连通最小代价用 MST（稠密 Prim/稀疏 Kruskal）；依赖顺序/判有向环用拓扑；两点路径用最短路。✅ 正确
排除法：无（判断题）。混淆点：按"目标"选算法，不按"感觉"。
关联 · G1 总表：三步选择法。
判断题：Kruskal 忘判环（不做 find 检查直接 union）会得到带环的"树"——结果不再是生成树。
考点：Kruskal 忘判环（H1）。
解析：忘判环（不做 find 检查直接 union）会得到带环的"树"——结果不再是生成树。✅ 正确
排除法：无（判断题）。混淆点：P2 实证——全部边加起来 16。
关联 · P2 代码：忘判环输出 16。
判断题：Kahn 拓扑忘写"出边终点入度减 1"，队列只会输出最初入度 0 的点——结果严重不全。
考点：拓扑忘减入度（H2）。
解析：Kahn 忘写"出边终点入度减 1"，队列只会输出最初入度 0 的点——结果严重不全。✅ 正确
排除法：无（判断题）。混淆点：P3 实证——只输出 1。
关联 · P3 代码：忘减入度输出 1。
判断题：Prim 的更新式是 ；若误写成 Dijkstra 的 ，MST 代价会算错。
考点：Prim 与 Dijkstra 混淆（H3）。
解析：Prim 的更新式是 ；误写成 Dijkstra 的 ，MST 代价会算错。✅ 正确
排除法：无（判断题）。混淆点：P4 实证——得 10 而非 5。
关联 · P4 代码：两式只差一个加号。
判断题：重边保留最小权即可（Kruskal 排序后天然处理）；自环不可能是 MST 边，Kruskal 判环时自动跳过。
考点：重边与自环（H4）。
解析：重边保留最小权即可（Kruskal 排序后天然处理）；自环不可能是 MST 边，Kruskal 判环时自动跳过。✅ 正确
排除法：无（判断题）。混淆点：自环两端同点 find 必同根 → 跳过。
关联 · N6 大综合：重边 (1,3,7) 被跳过。
判断题：以下结论全部正确——"生成树 条边；Prim 的 d 是到集合的最小边权；Kruskal 先排序再并查集判环；拓扑 Kahn 入度 0 入队、输出 判环；MST 不保证两点最短路"。
考点：综合判断（H5）。
解析：五结论全对——生成树 条边；Prim 的 d 是到集合的最小边权；Kruskal 先排序再并查集判环；拓扑 Kahn 入度 0 入队、输出 判环；MST 不保证两点最短路。✅ 正确
排除法：无（判断题）。混淆点：本章核心结论自检清单。
关联 · 本章全部核心结论：收官判断题。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int n = 4; 05 int w[5][5]; 06 memset(w, 0x3f, sizeof w); 07 w[1][2] = w[2][1] = 2; w[1][3] = w[3][1] = 5; 08 w[2][3] = w[3][2] = 1; w[2][4] = w[4][2] = 6; 09 w[3][4] = w[4][3] = 2; 10 int d[5], vis[5] = {0}; 11 memset(d, 0x3f, sizeof d); 12 d[1] = 0; 13 int ans = 0; 14 for (int it = 0; it < n; it++) { 15 int u = -1; 16 for (int i = 1; i <= n; i++) 17 if (!vis[i] && (u == -1 || d[i] < d[u])) u = i; 18 vis[u] = 1; 19 ans += d[u]; 20 for (int v = 1; v <= n; v++) 21 if (!vis[v] && w[u][v] != 0x3f3f3f3f && d[v] > w[u][v]) 22 d[v] = w[u][v]; 23 } 24 cout << ans; 25 return 0; 26}
单选题：程序输出是？（MST 总代价）
考点：朴素 Prim 代码输出（I1）。
解析：图（无向）：(1,2,2)(1,3,5)(2,3,1)(2,4,6)(3,4,2)。加入序 1→2→3→4：d[2]=2、d[3] 被 2 压到 1、d[4] 被 3 压到 2——ans = 0+2+1+2 = 5。✅ 答案 A
排除法：B/C/D 把某条边算重或算错。
关联 · B2 步骤：选点—加价—更新。
// 图与 I1 完全相同，循环体内在 vis[u] = 1 之后加一句： cout << u << " ";
单选题：程序输出是？（点加入树的顺序）
考点：点加入顺序（I2）。
解析：d 序列 0,2,1,2 递增选择：1 → 2（d=2）→ 3（d=1）→ 4（d=2）。✅ 答案 B
排除法：A/C/D 顺序与 d 变化不符。
关联 · B1 思想：离集合最近者先加入。
01// 图与 I1 完全相同，最后输出 d 数组： 02for (int i = 1; i <= n; i++) cout << d[i] << " ";
单选题：程序输出是？（d[i] = 点 i 加入时的代价，即到已选集合的最小边权）
考点：d 数组语义（I3）。
解析：d = 各点加入时的代价（到已选集合的最小边权）：d[3]=1 不是 5——被 2-3 这条边压小。✅ 答案 C
排除法：A 的 5 是 1-3 直达边权（非最小）；B/D 是其他图的数。
关联 · B4 与 Dijkstra 对比：d 语义是集合距离。
01// 图与 I1 完全相同，循环体内在 vis[u] = 1 后加： 02if (u == 2) { // 刚加入 2 号点时 03 for (int i = 1; i <= n; i++) cout << d[i] << " "; 04}
单选题：程序输出是？
考点：过程快照（I4）。
解析：刚加入 2 时已用 2 的边更新过：d[3]=min(5,1)=1、d[4]=6——快照 0 2 1 6。✅ 答案 A
排除法：B 是 Dijkstra 式 d+2；C 漏了 3 的更新；D 是最终值。
关联 · I3：快照 vs 最终。
01vis[u] = 1; 02ans += d[u]; 03for (int v = 1; v <= n; v++) 04 if (w[u][v] != 0x3f3f3f3f && d[v] > ______) 05 d[v] = ______; // 用边权直接更新
单选题：横线处应填入？
考点：更新式（I5）。
解析：Prim 用边权本身更新（到集合的最小边权）：w[u][v]。✅ 答案 A
排除法：B 是 Dijkstra 式；C 无意义自比较；D 无关。
关联 · H3/P4：加不加 d[u] 是两算法分水岭。
// 图与 I1 基本相同，只有 3-4 这条边权改成 3： w[3][4] = w[4][3] = 3;
单选题：程序输出是？（MST 总代价）
考点：边权变化后重算（I6）。
解析：3-4 改成 3：MST 边 (2,3,1)(1,2,2)(3,4,3) = 6。✅ 答案 B
排除法：A 5 是原图；C/D 无依据。
关联 · I1：同法不同图。
01#include <bits/stdc++.h> 02using namespace std; 03struct Edge { int u, v, w; }; 04int fa[5]; 05int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } 06int main() { 07 int n = 4; 08 vector<Edge> e = {{1,2,2}, {1,3,5}, {2,3,1}, {2,4,6}, {3,4,2}}; 09 sort(e.begin(), e.end(), [](Edge a, Edge b) { return a.w < b.w; }); 10 for (int i = 1; i <= n; i++) fa[i] = i; 11 int ans = 0; 12 for (auto [u, v, w] : e) { 13 if (find(u) != find(v)) { 14 fa[find(u)] = find(v); 15 ans += w; 16 } 17 } 18 cout << ans; 19 return 0; 20}
单选题：程序输出是？
考点：标准 Kruskal（J1）。
解析：排序后 (2,3,1)(1,2,2)(3,4,2)(1,3,5)(2,4,6)，前三边连通全部点，ans = 1+2+2 = 5。✅ 答案 C
排除法：A 7 是 1+2+... 算错；B 6 含 (1,3)；D 漏边。
关联 · C2 步骤：排序—判环—合并。
01// 图与 J1 完全相同，取边时输出该边权值： 02if (find(u) != find(v)) { 03 fa[find(u)] = find(v); 04 cout << w << " "; 05}
单选题：程序输出是？（被选入 MST 的边的权值序列）
考点：选入边的权值序列（J2）。
解析：入选边 (2,3,1)(1,2,2)(3,4,2) → 权值 1 2 2。✅ 答案 D
排除法：A 的 5 是被跳过的边；B 顺序反；C 的 6 未入选。
关联 · C1 思想：从小到大取不连通的边。
01#include <bits/stdc++.h> 02using namespace std; 03struct Edge { int u, v, w; }; 04int fa[5]; 05int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } 06int main() { 07 int n = 4; 08 vector<Edge> e = {{1,2,2}, {2,3,1}, {3,4,2}, {1,4,3}, {1,3,5}}; 09 sort(e.begin(), e.end(), [](Edge a, Edge b) { return a.w < b.w; }); 10 for (int i = 1; i <= n; i++) fa[i] = i; 11 int skip = 0; 12 for (auto [u, v, w] : e) { 13 if (find(u) != find(v)) fa[find(u)] = find(v); 14 else skip++; // 两端已连通，成环跳过 15 } 16 cout << skip; 17 return 0; 18}
单选题：程序输出是？（被跳过（会成环）的边数）
考点：判环跳过的边数（J3）。
解析：排序 (2,3,1)(1,2,2)(3,4,2)(1,4,3)(1,3,5)：前三边入选后，(1,4,3) 与 (1,3,5) 两端均已连通 → 跳过 2 条。✅ 答案 A
排除法：B 不判环；C/D 数错。
关联 · C3 并查集判环：同根即跳。
01#include <bits/stdc++.h> 02using namespace std; 03int fa[5] = {0, 2, 3, 4, 4}; // 链：1 -> 2 -> 3 -> 4 04int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } 05int main() { 06 find(1); // 查找 1 的代表元，触发路径压缩 07 cout << fa[1] << " " << fa[2] << " " << fa[3]; 08 return 0; 09}
单选题：程序输出是？
考点：路径压缩效果（J4）。
解析：链 1→2→3→4 上 find(1) 后，1、2、3 的 fa 全部直接指向根 4。✅ 答案 B
排除法：A 是压缩前；C 3 未压缩（实际会被压缩）；D 无依据。
关联 · O3 填空：
fa[x] = find(fa[x])。
01for (auto [u, v, w] : e) { 02 if (find(u) != find(v)) { 03 ______; // 合并两集合 04 ans += w; 05 } 06}
单选题：横线处应填入？
考点：合并语句（J5）。
解析：把 u 的根挂到 v 的根下：fa[find(u)] = find(v)。✅ 答案 A
排除法：B 只挂节点不挂根（可能断链）；C 语法错；D 方向反。
关联 · J4：合并要挂在根上。
// 图与 J1 完全相同，取边时 cnt++，最后输出： cout << cnt << " " << ans;
单选题：程序输出是？（取边数与总代价）
考点：取边数与总代价（J6）。
解析：生成树恰取 n−1 = 3 条边，总代价 5。✅ 答案 C
排除法：A 的 6 错；B 取 4 条成环；D 漏边。
关联 · A2 生成树性质：n−1 条边。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int n = 4; 05 vector<int> g[5]; 06 int indeg[5] = {0}; 07 g[1].push_back(2); g[1].push_back(3); 08 g[2].push_back(4); 09 g[3].push_back(4); 10 for (int u = 1; u <= n; u++) 11 for (int v : g[u]) indeg[v]++; 12 queue<int> q; 13 for (int i = 1; i <= n; i++) 14 if (indeg[i] == 0) q.push(i); 15 while (!q.empty()) { 16 int u = q.front(); q.pop(); 17 cout << u << " "; 18 for (int v : g[u]) 19 if (--indeg[v] == 0) q.push(v); 20 } 21 return 0; 22}
单选题：程序输出是？（拓扑序）
考点：BFS 版拓扑（K1）。
解析：入度 0 的只有 1；出队 1 后 2、3 入度变 0 入队；依次 2、3 把 4 的入度减到 0。输出 1 2 3 4。✅ 答案 A
排除法：B 需换邻接顺序；C/D 不满足依赖。
关联 · D3 Kahn 步骤：入度 0 入队—减度—再入队。
// 图与 K1 的唯一区别：1 号点的邻接顺序不同—— g[1].push_back(3); g[1].push_back(2);
单选题：程序输出是？（换邻接顺序后队列顺序改变，拓扑序合法但不同）
考点：多解性实证（K2）。
解析：1 的邻接改为先 3 后 2 → 队列 [3,2] → 输出 1 3 2 4——同一 DAG 的另一个合法拓扑序。✅ 答案 D
排除法：A 是 K1 的序；B 4 在 2 前不合法；C 无依据。
关联 · D5 多解性：顺序可变、合法性不变。
01// 图与 K1 完全相同，每出队一个点后输出 indeg[4]： 02while (!q.empty()) { 03 int u = q.front(); q.pop(); 04 for (int v : g[u]) 05 if (--indeg[v] == 0) q.push(v); 06 cout << indeg[4] << " "; 07}
单选题：程序输出是？（每出队一个点后 4 号点的入度）
考点：4 号点入度变化（K3）。
解析：indeg[4] 初值 2；出队 1 不动它（=2）、出队 2 减到 1、出队 3 减到 0、出队 4 仍 0——输出 2 1 0 0（每出队一次打印一次）。✅ 答案 A
排除法：B 漏最后一次打印；C/D 数值错。
关联 · D2 入度概念：入度归零才能做。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int n = 3; 05 vector<int> g[4]; 06 int indeg[4] = {0}; 07 g[1].push_back(2); 08 g[2].push_back(3); 09 g[3].push_back(1); // 有环：1 -> 2 -> 3 -> 1 10 for (int u = 1; u <= n; u++) 11 for (int v : g[u]) indeg[v]++; 12 queue<int> q; 13 for (int i = 1; i <= n; i++) 14 if (indeg[i] == 0) q.push(i); 15 int cnt = 0; 16 while (!q.empty()) { 17 int u = q.front(); q.pop(); 18 cnt++; 19 for (int v : g[u]) 20 if (--indeg[v] == 0) q.push(v); 21 } 22 if (cnt < n) cout << "CYCLE"; 23 return 0; 24}
单选题：程序输出是？
考点：Kahn 判环（K4）。
解析：环 1→2→3→1 上每个点入度都 ≥1，无人入队 → cnt=0 < 3 → 输出 CYCLE。✅ 答案 A
排除法：B/C/D 都不是本程序输出。
关联 · D4 判环：输出 < n ⟺ 有环。
01int u = q.front(); q.pop(); 02cnt++; 03for (int v : g[u]) { 04 if (______ == 0) q.push(v); // 入度减 1 后为 0 才入队 05}
单选题：横线处应填入？
考点：减入度并判断（K5）。
解析：先减后判断：--indeg[v] == 0（减到 0 才入队）。✅ 答案 A
排除法：B 不减入度；C 是后置减（判断的是减前值）；D 方向反。
关联 · O6 填空：同一行的拆分考法。
01// 图与 K1 完全相同，只是队列换成小根堆： 02priority_queue<int, vector<int>, greater<int>> q; 03for (int i = 1; i <= n; i++) 04 if (indeg[i] == 0) q.push(i); 05while (!q.empty()) { 06 int u = q.top(); q.pop(); 07 cout << u << " "; 08 for (int v : g[u]) 09 if (--indeg[v] == 0) q.push(v); 10}
单选题：程序输出是？（字典序最小的拓扑序）
考点：小根堆求字典序最小拓扑序（K6）。
解析：pq 每次取编号最小的入度 0 点：1 → 2（2 < 3）→ 3 → 4。输出 1 2 3 4。✅ 答案 C
排除法：A 是普通队列换序的；B/D 不满足依赖或非最小。
关联 · F5 字典序最小：堆换队列。
// 图与 K1 完全相同，最后输出： cout << cnt << endl; // cnt = 已输出的点数 // 输出顺序已在出队时打印
单选题：程序输出是？（第一行 = 输出点数，第二行 = 拓扑序）
考点：点数与顺序（K7）。
解析：cnt = 4（全部输出），拓扑序 1 2 3 4。✅ 答案 A
排除法：B 序不同；C 点数错；D 顺序不合法。
关联 · K1：同图同法。
01#include <bits/stdc++.h> 02using namespace std; 03struct Edge { int u, v, w; }; 04int fa[5]; 05int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } 06int main() { 07 int n = 4; 08 vector<Edge> e = {{1,2,2}, {1,3,5}, {2,3,1}, {2,4,6}, {3,4,2}}; 09 sort(e.begin(), e.end(), [](Edge a, Edge b) { return a.w > b.w; }); // 降序 10 for (int i = 1; i <= n; i++) fa[i] = i; 11 int ans = 0; 12 for (auto [u, v, w] : e) 13 if (find(u) != find(v)) { 14 fa[find(u)] = find(v); 15 ans += w; 16 } 17 cout << ans; 18 return 0; 19}
单选题：程序输出是？（最大生成树总代价）
考点：降序排序（L1）。
解析：降序取边 (2,4,6)(1,3,5)(3,4,2) = 13。✅ 答案 B
排除法：A 5 是最小生成树；C/D 无依据。
关联 · E2 最大生成树：排序反转即可。
01// 图与 I1 相同。最小生成树的边为 (2,3,1)、(1,2,2)、(3,4,2)。 02// 瓶颈路 = MST 上两点路径的最大边权，本题求 MST 的最大边权： 03int mx = 0; 04for (auto [u, v, w] : mstEdges) mx = max(mx, w); 05cout << mx;
单选题：程序输出是？
考点：MST 最大边（L2）。
解析：MST 边权 {1,2,2}，最大边 = 2——即全图"最小化最大边权"的答案。✅ 答案 D
排除法：A 是最小边；B 是总代价；C 无依据。
关联 · E4 瓶颈路：MST 的另一个用途。
// 思想：枚举删掉 MST 上的一条边，求剩余图的 MST，取最小总代价。
// 图边：(1,2,2) (1,3,5) (2,3,1) (2,4,6) (3,4,2)，MST = {2-3:1, 1-2:2, 3-4:2} = 5
// 删 (2,3,1) → 剩余 MST = 1-2:2 + 3-4:2 + 1-3:5 = 9
// 删 (1,2,2) → 剩余 MST = 2-3:1 + 3-4:2 + 1-3:5 = 8
// 删 (3,4,2) → 剩余 MST = 2-3:1 + 1-2:2 + 2-4:6 = 9
// 次小生成树 = min(9, 8, 9) = 8
cout << 8;
单选题：程序输出是？
考点：删边重算（L3）。
解析：删 (2,3,1)→9、删 (1,2,2)→8、删 (3,4,2)→9，最小 8。✅ 答案 C
排除法：A 5 是最小生成树本身；B 9 是某次删边值；D 无依据。
关联 · E3 次小生成树思想：枚举替换。
01int cnt = 0; 02for (auto [u, v, w] : e) { 03 if (find(u) != find(v)) { 04 fa[find(u)] = find(v); 05 ans += w; 06 cnt++; 07 if (cnt == ______) break; // 取满 n-1 条边即可停止 08 } 09}
单选题：横线处应填入？
考点：提前停止条件（L4）。
解析：生成树 条边取满即可 break。✅ 答案 A
排除法：B n 条会成环（虽被并查集挡住）；C/D 无依据。
关联 · A2 生成树性质：n−1 条边。
01// n = 3，只有一条边 (1,2,1)：3 号点孤立，图不连通 02int n = 3; 03vector<Edge> e = {{1,2,1}}; 04sort(e.begin(), e.end(), [](Edge a, Edge b) { return a.w < b.w; }); 05for (int i = 1; i <= n; i++) fa[i] = i; 06int ans = 0, cnt = 0; 07for (auto [u, v, w] : e) 08 if (find(u) != find(v)) { 09 fa[find(u)] = find(v); 10 ans += w; cnt++; 11 } 12if (cnt < n - 1) cout << "IMPOSSIBLE"; 13else cout << ans;
单选题：程序输出是？
考点：不连通图无 MST（L5）。
解析：3 个点只有一条边，cnt=1 < n−1=2 → 输出 IMPOSSIBLE。✅ 答案 D
排除法：A 1 是已取代价；B/C 无依据。
关联 · A1 定义：MST 要求连通。
// 图与 J1 完全相同，最后输出： cout << ans << " " << cnt; // cnt = 取边数
单选题：程序输出是？
考点：代价与边数（L6）。
解析：ans = 5、cnt = 3。✅ 答案 B
排除法：A 边数错；C 代价错；D 边数错。
关联 · J6：同图不同输出格式。
// 课程先修：1 先于 2、1 先于 3、2 先于 4、3 先于 4 // 图与 K1 完全相同，输出拓扑序
单选题：程序输出是？（一个合法的选课顺序）
考点：先修关系拓扑（M1）。
解析：先修 1→2、1→3、2→4、3→4，拓扑序 1 2 3 4（或 1 3 2 4）。✅ 答案 A
排除法：B 也是合法序但代码按邻接顺序输出 A；C/D 不合法。
关联 · F1 课程安排：先修指向后修。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int n = 4; 05 vector<pair<int,int>> g[5]; 06 int indeg[5] = {0}; 07 g[1].push_back({2, 2}); g[1].push_back({3, 3}); 08 g[2].push_back({4, 4}); 09 g[3].push_back({4, 1}); 10 for (int u = 1; u <= n; u++) 11 for (auto [v, w] : g[u]) indeg[v]++; 12 queue<int> q; 13 for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push(i); 14 int dist[5] = {0}; 15 while (!q.empty()) { 16 int u = q.front(); q.pop(); 17 for (auto [v, w] : g[u]) { 18 dist[v] = max(dist[v], dist[u] + w); // 拓扑序 DP 求最长路 19 if (--indeg[v] == 0) q.push(v); 20 } 21 } 22 cout << dist[4]; 23 return 0; 24}
单选题：程序输出是？（1 到 4 的最长路）
考点：拓扑序 DP 求最长路（M2）。
解析：dist[4] = max(2+4, 3+1) = 6（走 1→2→4）。✅ 答案 C
排除法：A 5 是 3+... 算错；B 4 漏了 2+4；D 无依据。
关联 · F4 关键路径思想：min 换 max。
// 依赖关系成环：1 依赖 2、2 依赖 3、3 依赖 1（边 1<-2, 2<-3, 3<-1） // 建边 2->1, 3->2, 1->3 后 Kahn 输出点数 < n，输出： cout << "NO";
单选题：程序输出是？（存在循环依赖）
考点：循环依赖检测（M3）。
解析：依赖成环（1→2→3→1）→ Kahn 输出不完 → NO。✅ 答案 B
排除法：A 只在无环；C 是 K4 的输出词；D 无依据。
关联 · F2 依赖冲突：环 = 冲突。
01for (auto [v, w] : g[u]) { 02 dist[v] = max(dist[v], ______); // 经 u 到 v 的更长路 03 if (--indeg[v] == 0) q.push(v); 04}
单选题：横线处应填入？
考点：最长路转移（M4）。
解析：经 u 到 v 的距离 = dist[u] + w，取 max。✅ 答案 A
排除法：B 漏边权；C 漏前驱距离；D 自比较。
关联 · M2：转移式即答案。
// 图与 M2 相同（先修关系不变），用小根堆求字典序最小拓扑序
单选题：程序输出是？
考点：堆求字典序最小（M5）。
解析：pq 每次取编号最小的入度 0 点：出队 1 后 {2,3} 都入堆，取编号小的 2；2 把 4 的入度减到 1，3 再减到 0 入堆；最后 4。输出 1 2 3 4。✅ 答案 D
排除法：A 是普通队列换序的结果；B 首点非最小；C 4 在 3 前不满足依赖。
关联 · K6：同图同法。
01// 图与 M2 完全相同（含边权），拓扑序 DP 求最长路后输出整个 dist： 02for (int i = 1; i <= n; i++) cout << dist[i] << " ";
单选题：程序输出是？
考点：最长路 dist 数组（M6）。
解析：dist = [0, 2, 3, 6]（1 起点 0，2←2，3←3，4←max(2+4, 3+1)=6）。✅ 答案 A
排除法：B 的 5 把 4 按最短路思维算了；C 顺序反；D 无依据。
关联 · M2：整表输出。
// 图与 I1 完全相同，但起点换成 2（d[2] = 0）：
单选题：程序输出是？（MST 总代价与起点无关）
考点：MST 与起点无关（N1）。
解析：从 2 出发 Prim 仍得 5——MST 代价与起点选择无关。✅ 答案 A
排除法：B/C/D 无依据。
关联 · B1 思想：起点任意。
// 图与 J1 完全相同（标准 Kruskal），输出总代价
单选题：程序输出是？
考点：标准 Kruskal（N2）。
解析：边排序 (2,3,1)(1,2,2)(3,4,2)(1,3,5)(2,4,6)，前三条连通全部 4 个点，ans = 1+2+2 = 5。✅ 答案 B
排除法：A 4 漏了边；C 6 误取 (1,3,5)；D 13 是最大生成树。
关联 · J1：模板默写。
01#include <bits/stdc++.h> 02using namespace std; 03vector<int> g[5]; 04int vis[5]; 05void dfs(int u) { // DFS 版拓扑排序：后序压栈 06 vis[u] = 1; 07 for (int v : g[u]) if (!vis[v]) dfs(v); 08 cout << u << " "; // 后序：离开时输出 09} 10int main() { 11 g[1].push_back(2); g[1].push_back(3); 12 g[2].push_back(4); 13 g[3].push_back(4); 14 dfs(1); 15 return 0; 16}
单选题：程序输出是？（后序输出的逆序才是拓扑序；本题直接问后序输出）
考点：DFS 后序输出（N3）。
解析：dfs(1)：先深入 2→4（输出 4、2），再 3（4 已访问，输出 3），最后输出 1——后序 4 2 3 1（反转才是拓扑序 1 3 2 4）。✅ 答案 C
排除法：A 是 BFS 序；B 是整体反转；D 无依据。
关联 · D6 DFS 思想：后序 + 反转。
// 同一张无向图（边同 I1）：先 Kruskal 求 MST 代价，再 Dijkstra 求 1 到 4 最短路： cout << mstCost << " " << dist[4];
单选题：程序输出是？
考点：同图两问（N4）。
解析：MST 代价 5；Dijkstra 1→4 最短路 = min(8, 7, 5) = 5（走 1-2-3-4）——两值恰巧相同。✅ 答案 D
排除法：A/B 的 7 是 1-3-4；C 无依据。
关联 · A5 与最短路区别：同值纯属巧合。
01sort(e.begin(), e.end(), [](Edge a, Edge b) { 02 return ______; // 按边权升序 03});
单选题：横线处应填入？
考点：排序比较器（N5）。
解析：升序 a.w < b.w。✅ 答案 A
排除法：B 降序（最大生成树）；C 按端点排（错）；D 恒真（排序失效）。
关联 · C7 必须先排序：比较器方向决定贪心方向。
// 图：4 个点，边 (1,2,2) (2,3,1) (3,4,2) (1,3,5) (2,4,6) 外加一条重边 (1,3,7) // 标准 Kruskal，统计 skip（判环跳过的边数）与 ans，输出： cout << skip << " " << ans;
单选题：程序输出是？
考点：重边 + 判环统计（N6）。
解析：入选 (2,3,1)(1,2,2)(3,4,2)；跳过的边 (1,3,5)(2,4,6)(1,3,7) 共 3 条；ans = 5。✅ 答案 B
排除法：A 漏重边；C/D 无依据。
关联 · H4 重边自环：重边最小权天然胜出。
01int n, m; 02int w[N][N], d[N], vis[N]; 03 04int prim(int s) { 05 memset(d, 0x3f, sizeof d); 06 memset(vis, 0, sizeof vis); 07 d[s] = 0; 08 int ans = 0; 09 for (int it = 0; it < n; it++) { 10 int u = -1; 11 for (int i = 1; i <= n; i++) 12 if (!vis[i] && (u == -1 || ①)) u = i; // 选 d 最小的未加入点 13 vis[u] = 1; 14 ans += d[u]; 15 for (int v = 1; v <= n; v++) 16 if (!vis[v] && w[u][v] != INF && d[v] > w[u][v]) d[v] = w[u][v]; 17 } 18 return ans; 19}
单选题：①处应填？
考点：选点条件（O1）。
解析：选未加入中 d 最小的点：d[i] < d[u]。✅ 答案 A
排除法：B 选最大；C 语义错；D 已访问才选（反了）。
关联 · B2 步骤：选点—标记—更新。
01vis[u] = 1; 02ans += d[u]; 03for (int v = 1; v <= n; v++) 04 if (w[u][v] != INF && d[v] > ②) 05 d[v] = ②; // 到已选集合的最小边权
单选题：②处应填？
考点：更新值（O2）。
解析：用边权本身：w[u][v]。✅ 答案 C
排除法：A 是 Dijkstra 式；B 漏边权；D 无关。
关联 · H3/P4：与 Dijkstra 的分水岭。
01int find(int x) { 02 return fa[x] == x ? x : ①; // 路径压缩 03}
单选题：①处应填？
考点：路径压缩 find（O3）。
解析：递归 + 赋值压缩：fa[x] = find(fa[x])。✅ 答案 B
排除法：A 不压缩（下次还爬链）；C 死递归；D 返回父亲不返回根。
关联 · J4 代码：压缩效果 4 4 4。
01for (auto [u, v, w] : e) { 02 if (①) { // 两端不连通才取这条边 03 fa[find(u)] = find(v); 04 ans += w; 05 } 06}
单选题：①处应填？
考点：判环条件（O4）。
解析：两端不同根才取边：find(u) != find(v)。✅ 答案 A
排除法：B 同根才取（专取成环边）；C 只比编号；D 比的是非根父亲。
关联 · C3 并查集判环：同根即环。
01queue<int> q; 02for (int i = 1; i <= n; i++) 03 if (①) q.push(i); // 初始入度为 0 的点入队
单选题：①处应填？
考点：初始入队条件（O5）。
解析：入度为 0 的点入队：indeg[i] == 0。✅ 答案 D
排除法：A/B 方向反；C 与入度无关。
关联 · D3 Kahn 步骤：初始入队。
01int u = q.front(); q.pop(); 02cnt++; 03for (int v : g[u]) { 04 ①; // 终点入度减 1 05 if (indeg[v] == 0) q.push(v); 06}
单选题：①处应填？
考点：减入度（O6）。
解析：终点入度减 1：--indeg[v]（先减后用）。✅ 答案 A
排除法：B 减错对象；C 加；D 减错对象。
关联 · K5 填空：同句两考。
01while (!q.empty()) { ... cnt++; ... } 02if (①) cout << "CYCLE"; // 输出点数不足 n，有环
单选题：①处应填？
考点：判环条件（O7）。
解析：输出点数不足 n：cnt < n。✅ 答案 B
排除法：A 只在无环；C/D 语义错。
关联 · D4 判环：cnt 与 n 比较。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int n = 4; 05 int w[5][5]; 06 memset(w, 0x3f, sizeof w); 07 w[1][2] = w[2][1] = 2; w[1][3] = w[3][1] = 5; 08 w[2][3] = w[3][2] = 1; w[2][4] = w[4][2] = 6; 09 w[3][4] = w[4][3] = 2; 10 int d[5], vis[5] = {0}; 11 memset(d, 0x3f, sizeof d); 12 d[1] = 0; 13 int ans = 0; 14 for (int it = 0; it < n; it++) { 15 int u = -1; 16 for (int i = 1; i <= n; i++) 17 if (!vis[i] && (u == -1 || d[i] < d[u])) u = i; 18 // 注意：这里漏掉了 vis[u] = 1; 19 ans += d[u]; 20 for (int v = 1; v <= n; v++) 21 if (!vis[v] && w[u][v] != 0x3f3f3f3f && d[v] > w[u][v]) 22 d[v] = w[u][v]; 23 } 24 cout << ans; 25 return 0; 26}
单选题：程序输出是？（正确结果应为 5）
考点：漏写 vis[u]=1 的后果（P1）。
解析：d[1]=0 永远最小，每轮重选 1——ans = 0+0+0+0 = 0，其余点虽被更新但从未计入。✅ 答案 A
排除法：B 是正确结果；C/D 无依据。
关联 · B2 步骤：标记是算法的一部分。
01// 图与 J1 完全相同，但取边时不判环，直接合并： 02for (auto [u, v, w] : e) { 03 fa[find(u)] = find(v); // 注意：没有 if (find(u) != find(v)) 04 ans += w; 05}
单选题：程序输出是？（正确结果应为 5）
考点：不判环直接合并（P2）。
解析：5 条边全被加入：2+1+2+5+6 = 16——结果带环、不是树。✅ 答案 D
排除法：A 5 是正确结果；B 13 是最大生成树；C 无依据。
关联 · H1 忘判环：概念题对应实证。
01// 图与 K1 完全相同，但出队后漏写了 --indeg[v]： 02while (!q.empty()) { 03 int u = q.front(); q.pop(); 04 cout << u << " "; 05 for (int v : g[u]) { 06 // 注意：漏掉了 indeg[v]--，也没有入队判断 07 } 08}
单选题：程序输出是？（正确应输出 4 个点 1 2 3 4）
考点：漏写 --indeg[v] 的后果（P3）。
解析：只有初始入度 0 的点 1 能出队，其余点入度永不为 0——输出 1（只 1 个点）。✅ 答案 B
排除法：A 4 是正确点数；C/D 无依据。
关联 · H2 忘减入度：概念题对应实证。
01// 图与 I1 完全相同，但更新写成了 Dijkstra 式： 02for (int v = 1; v <= n; v++) 03 if (!vis[v] && w[u][v] != 0x3f3f3f3f && d[v] > d[u] + w[u][v]) 04 d[v] = d[u] + w[u][v]; // 注意：d[u] + w 而非 w
单选题：程序输出是？（正确 MST 代价应为 5）
考点：误用 Dijkstra 式 d[u]+w（P4）。
解析：d[3]=min(5, 2+1)=3、d[4]=min(8, 3+2)=5——ans = 0+2+3+5 = 10（正确 5）。✅ 答案 C
排除法：A 5 是正确结果；B/D 无依据。
关联 · H3 Prim/Dijkstra 混淆：一个加号差一倍。
01// 图与 J1 完全相同，但排序写成了降序： 02sort(e.begin(), e.end(), [](Edge a, Edge b) { return a.w > b.w; });
单选题：程序输出是？（正确最小生成树代价应为 5）
考点：降序排序的后果（P5）。
解析：降序取边 (2,4,6)(1,3,5)(3,4,2) = 13——得到的是最大生成树。✅ 答案 A
排除法：B 5 是正确 MST；C 16 是全边和；D 无依据。
关联 · E2 最大生成树：降序 = 最大。
判断题：以下五种易错写法都会导致程序出错——①Prim 忘写 vis[u] = 1（反复选起点）②Kruskal 不判环直接合并（结果带环）③拓扑排序忘减入度（只输出最初入度 0 的点）④Prim 误用 Dijkstra 更新式 d[u]+w（代价算错）⑤Kruskal 排序写成降序（得到最大生成树）。
考点：五种易错写法综合判断（P6）。
解析：五条全对——忘 vis 标记反复选起点、不判环直接合并、忘减入度只输出 1 个点、误用 d[u]+w 得 10、降序得最大生成树 13。✅ 正确
排除法：无（判断题）。混淆点：每条对应本章一个代码题（P1~P5）实证。
关联 · P1~P5：易错清单自查。