从《岛屿个数》到《砍树》：聊聊蓝桥杯C++ B组里那些考验‘图论’思维的题

蓝桥杯C++ B组图论题精讲：从岛屿计数到树上路径的算法实战

在算法竞赛的进阶之路上，图论问题往往成为区分选手水平的关键分水岭。蓝桥杯省赛C++ B组近年来的压轴题目，几乎都被精心设计的图论问题所占据。这些题目表面看是考察具体场景的应用能力，实则是对图论核心思维的系统性检验。本文将带您深入剖析三个典型题目——《岛屿个数》《景区导游》和《砍树》，揭示它们背后共通的算法逻辑与解题范式。

1. 图论问题在竞赛中的典型呈现方式

算法竞赛中的图论问题很少直接以"求最短路径"或"计算连通分量"这样教科书式的方式出现。命题者更倾向于将图论概念嵌入到具象场景中，考验选手的问题抽象能力。《岛屿个数》看似是二维矩阵处理，《景区导游》伪装成旅游路线规划，《砍树》表面是 forestry 操作——这些都需要快速识别出图论本质。

以2023年蓝桥杯省赛为例，图论相关题目占比达到30%，且全部出现在编程大题部分。我们统计了近三年考点分布：

这三个题目完美展现了图论考察的三个层次：基础遍历、高级树算法和综合应用。理解这种命题思路，就能在比赛中快速抓住问题本质。

2. 《岛屿个数》的双重DFS解法剖析

这道题看似简单的连通分量计数，实则暗藏玄机。常规的岛屿问题只需统计连通区域数量，但本题特别提出了"子岛屿"概念——完全被另一个岛屿包围的岛屿不应被单独计数。这要求我们发展出更精细的遍历策略。

2.1 算法核心：海洋视角的渗透扫描

传统解法从陆地出发进行DFS/BFS，但这种方法无法判断包含关系。创新解法改为从外海出发扫描：

void dfs_0(int r, int c) { // 从海洋开始的扫描 st[r][c] = true; // 八方向连通搜索 for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) { int x = r + i, y = c + j; if (x < 0 || x > n + 1 || y < 0 || y > m + 1 || st[x][y]) continue; if (g[x][y] == 0) dfs_0(x, y); // 继续海洋遍历 else dfs_1(x, y), res++; // 发现新岛屿 } }

这个解法有两大精妙之处：

1. 地图预处理：在原始地图外围人工添加一圈海洋(0)，确保扫描起点
2. 双重DFS：用八连通扫描海洋，四连通扫描陆地，准确识别岛屿包含关系

2.2 易错点与验证技巧

在实际编码时，有几个关键细节需要注意：

• 海洋必须使用八连通遍历（允许斜向移动）
• 陆地必须使用四连通遍历（仅上下左右）
• 访问标记数组需要分开维护或在遍历后重置

提示：当遇到复杂矩阵遍历问题时，不妨考虑添加"哨兵"边界，这能极大简化边界条件处理。

3. 《景区导游》的LCA高效解法

景区路线问题本质上是树结构上的路径查询优化。给定一棵包含N个景点的树和K个待访问景点，要求计算跳过每个景点时的总路径长度。暴力解法复杂度O(K^2)显然无法通过大规模数据。

3.1 最近公共祖先(LCA)的预处理

LCA算法能在O(logN)时间内查询任意两点的最近公共祖先，是解决树上路径问题的利器。首先需要进行二进制提升预处理：

void dfs(int u, int fa) { depth[u] = depth[fa] + 1; f[u][0] = fa; // 二进制提升表预处理 for (int i = 1; i <= 19; i++) f[u][i] = f[f[u][i - 1]][i - 1]; // 递归处理子树 for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; d[j] = d[u] + w[i]; // 维护节点到根的距离 dfs(j, u); } }

预处理后，LCA查询采用二进制拆分法：

int lca(int a, int b) { if (depth[a] < depth[b]) swap(a, b); // 提升到同一深度 for (int i = 19; ~i; i--) if (depth[f[a][i]] >= depth[b]) a = f[a][i]; if (a == b) return a; // 同步提升找LCA for (int i = 19; ~i; i--) if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i]; return f[a][0]; }

3.2 路径计算的数学表达

利用LCA和预计算的距离数组，任意两点路径长度可表示为：

路径长度 = d[u] + d[v] - 2 * d[lca(u,v)]

基于此，我们可以推导出跳过第i个景点时的总路径长度：

1. 原始总路径：sum(path(Ai, Ai+1)) for i=1 to K-1
2. 跳过Ai后的调整：
   • 移除path(Ai-1,Ai)和path(Ai,Ai+1)
   • 添加path(Ai-1,Ai+1)

for (int i = 0; i < k; i++) { LL res = sum; if (i && i != k - 1) // 非端点情况 res += get(q[i - 1], q[i + 1]) - get(q[i - 1], q[i]) - get(q[i], q[i + 1]); else if (!i) // 跳过第一个点 res -= get(q[i], q[i + 1]); else // 跳过最后一个点 res -= get(q[i - 1], q[i]); printf("%lld ", res); }

4. 《砍树》问题的树上差分解法

作为压轴题，《砍树》将图论推向了更高维度。题目要求找到一条边，使得砍掉它后，所有给定的点对都不连通。这需要结合LCA和树上差分两种高级技巧。

4.1 问题转化与算法选择

每个点对(u,v)给出的约束条件等价于：u到v的路径上的所有边都不能被砍。因此，我们需要：

1. 对所有点对计算其路径
2. 标记这些路径上的边
3. 找出未被任何路径覆盖的边（或编号最大的）

直接实现时间复杂度为O(M*N)，无法通过1e5规模的数据。这时就需要引入树上差分技术。

4.2 树上差分的实现步骤

1. 差分标记：对每个点对(u,v)，在u和v处+1，在LCA(u,v)处-2
2. 后缀求和：通过后序遍历累加子树标记和
3. 结果判定：边上的标记值等于M时，说明该边被所有路径覆盖

核心代码实现：

void dfs(int u, int fa) { for (auto v : e[u]) { if (v == fa) continue; int g = dfs(v, u); if (g == m) { // 找到满足条件的边 ans = max(ans, mp[{v, u}]); } res += g; } return res; } // 处理每个点对 for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; int z = lca(u, v); f[u]++; // 差分标记 f[v]++; f[z] -= 2; }

这种方法的精妙之处在于将O(M*N)的问题转化为O(M + N)的高效解法，展现了图论算法的强大威力。

5. 图论问题的通用解题框架

通过分析这三个典型题目，我们可以总结出解决竞赛图论问题的系统方法：

1. 问题抽象阶段

   • 识别图中的节点和边如何定义
   • 判断问题属于哪种图论经典模型（最短路、连通性、树问题等）
   • 评估数据规模，确定算法复杂度上限

2. 算法选择阶段

   • 基础遍历：DFS/BFS适用于连通性、 Flood Fill 类问题
   • 树结构问题：考虑LCA、树链剖分、树上差分等专门技术
   • 路径问题：Dijkstra、SPFA、Floyd等最短路算法

3. 优化实现阶段

   • 预处理加速：二进制提升、前缀和等
   • 空间优化：链式前向星存图
   • 边界处理：哨兵技巧、虚拟节点

4. 验证调试阶段

   • 设计小规模测试用例验证基本逻辑
   • 构造极端数据测试性能边界
   • 使用静态检查工具发现潜在错误

在竞赛准备过程中，建议建立自己的代码模板库，但更重要的是理解每个算法背后的核心思想。比如LCA算法虽然实现复杂，但其本质是二进制拆分思想的应用；树上差分看似神奇，实则是前缀和技巧在树结构上的延伸。