1. 从“危险系数”到图的割点一道蓝桥杯国赛题的深度拆解最近在整理历年蓝桥杯真题时又翻到了2013年第四届国赛C/C组国C的这道“危险系数”。题目名字听起来有点唬人像是要计算什么爆炸物的风险等级但实际上它是一道非常经典的图论问题考察的是对图的基本概念和算法灵活运用的能力。很多同学第一次看到题目描述里又是“地下交通站”又是“情报传递”可能会被场景带偏但其实核心就是在一个无向图中寻找那些“一旦被破坏就会导致两点间所有路径都中断”的关键节点。在专业术语里这类节点被称为“割点”或“关节点”。这道题之所以值得拿出来单独讲不是因为它算法多难核心就是DFS/BFS而是因为它完美地体现了竞赛题目如何将一个抽象的图论概念包装成一个生动的实际问题并考察选手能否透过现象看本质。同时在实现过程中有几个非常容易踩坑的细节比如对“所有路径”的理解、如何高效地判断一个点是否为割点、以及如何处理边界条件。今天我就结合当年的题目要求把这道题的解题思路、代码实现以及我调试过程中遇到的几个“坑”完整地复盘一遍希望能帮助正在备赛的你不仅会做这一道题更能掌握这类问题的通用思考方法。2. 题目场景还原与问题本质抽象我们先来彻底理解一下题目到底在问什么。根据回忆和常见的题目描述场景大致是这样的抗日战争时期我方有多个地下交通站有些站点之间是直接相连的构成了一张地下交通网络。现在我们需要从站点A向站点B传递一份情报。情报的传递必须沿着站点间的连接进行。问题是找出网络中的哪些站点除了起点A和终点B本身是“危险的”即如果这个站点被敌人破坏那么A和B之间就无法再进行任何形式的情报传递。2.1 第一步建立数学模型拿到这种描述第一步也是最重要的一步就是做“翻译”把文字描述映射成严谨的数据结构。顶点每个地下交通站自然对应图中的一个顶点。边两个交通站之间的直接连接对应图中的一条无向边。题目通常会给出所有连接的列表。问题在给定的无向图中给定源点A和汇点B求图中所有满足以下条件的顶点VV ≠ A, V ≠ B删除顶点V及其相连的所有边后图中A和B不再连通。这直接对应了图论中的一个核心概念对于连接点A和B来说顶点V是一个割点。更具体地说这里寻找的是A-B路径上的“必经之点”。2.2 关键点辨析必经点与全局割点这里有一个非常重要的细微差别也是初学者最容易混淆的地方。图论中一般的“割点”定义是删除该点后图的连通分量数量增加。这意味着这个点对整个图的连通性至关重要。但本题中的“危险系数”或“必经点”是相对于**一对特定的起点和终点A, B**而言的。举个例子假设图结构是 A—X—Y—B并且 X 还连接着另一个独立部分 Z即 Z 只和 X 相连。那么对于整个图来说X 是割点因为删除X后Z 就和主图分离了。但对于A和B而言呢删除X后A和B确实不连通了所以X是A-B的必经点。再看Y删除Y后A和B也不连通了所以Y也是A-B的必经点。但Y可能并不是整个图的割点如果Y只连接X和B的话。最后看Z它甚至不在任何一条A到B的路径上它根本不影响A和B的连通性。所以本题的目标是找出所有在A到B的路径上且是这些路径的公共交点的顶点。一个朴素但低效的想法是枚举每一个点除了A、B尝试删除它然后用DFS或BFS检查A和B是否还连通。时间复杂度是O(N*(NM))在N顶点数达到1000M边数较多时可能面临压力但通常蓝桥杯的数据规模下这种O(N²)的算法是可以通过的。不过我们完全可以追求更优解。2.3 输入输出格式与边界条件题目通常的输入格式是 第一行两个整数N, M分别表示站点数顶点数和通道数边数。顶点编号通常从1开始。 接下来M行每行两个整数u, v表示站点u和v之间有通道。 最后一行两个整数A, B表示起点和终点。 输出格式一个整数K表示危险系数的数目。如果没有即A和B直接相连或有其他不经过任何中间点的路径这里需注意则输出-1。需要特别注意的边界条件A和B直接相连如果图中存在边(A, B)那么即使删除任何其他点A和B依然连通通过这条直连边。所以答案应该是0不题目通常要求计算的是“中间站点”的危险系数。如果A和B直连那么不经过任何其他点就可以通信因此没有任何中间点是“必经的”。但输出-1还是0需要严格依据题目要求。经典描述是“如果没有满足条件的点则输出-1”。所以如果必经点集合为空则输出-1。A和B不连通这是最容易被忽略的如果一开始A和B就不连通那么根本就不存在传递情报的可能。这时任何一个点都不是“导致它们不连通”的原因因为它们本来就不连通。根据逻辑应该输出-1。在算法中我们需要先进行一次连通性判断。N的可能取值顶点数可能为1吗如果N1那么A和B只能是同一个点。这种情况一般不会出现在合法输入中但我们的程序要保证健壮性至少不能崩溃。3. 算法思路剖析两种实现路径的对比解决这个问题主要有两种清晰的思路一种是基于流量和路径计数的思路另一种是基于割点判定的思路。我分别介绍一下它们的原理和实现细节。3.1 思路一路径搜索与节点计数直观朴素法这是最符合直觉的方法。我们想要知道一个点V是不是A到B的必经点就看所有从A到B的路径是否都经过V。如何知道“所有路径”呢我们不可能枚举出指数级数量的所有路径。但可以换一个角度如果V是必经点那么删除V后A到B的路径数将变为0。如果V不是必经点那么删除V后至少还存在一条A到B的路径。因此算法可以设计如下首先在不删除任何点的情况下计算从A到B的路径总数或只需判断是否连通。如果不连通直接输出-1。然后依次枚举每一个候选点VV ≠ A, V ≠ B。在图中“删除”点V在DFS/BFS访问时跳过这个点再次计算从A到B的路径总数或判断连通性。如果删除V后A和B不连通了或路径数变为0那么V就是一个危险点必经点。复杂度分析需要运行N-2次DFS/BFS忽略A和B。每次DFS/BFS的时间复杂度是O(NM)。因此总时间复杂度为O(N*(NM))。在N≤1000, M≤10000的规模下运算量在10^7量级在竞赛的时限内通常1s是可行的尤其是用邻接表存储图和BFS搜索时。优点思路极其直观代码易于编写和调试不易出错。缺点效率是多项式级别对于极端大数据N10^5会超时。但蓝桥杯本题的数据规模通常允许此方法。3.2 思路二利用割点与DFS树Tarjan算法进阶应用这是一种更高效、更专业的图论方法时间复杂度接近O(NM)。其核心在于利用一次DFS计算出每个点的两个关键值dfn[i]深度优先搜索遍历序号和low[i]通过回边能追溯到的最早祖先的dfn。然后利用Tarjan算法判断割点的规则对于一个非根节点u如果存在一个子节点v满足low[v] dfn[u]那么u是割点。 对于根节点如果它有两个或以上的子节点那么它是割点。但是这判断的是全局割点。我们需要的是对于(A,B)的必经点。如何转化呢我们可以从A点开始进行DFS。在DFS的过程中我们关注B点。如果一个点u是A到B的必经点那么在DFS树上点u必然位于从A到B的路径上并且满足割点条件对于该条路径而言。更具体的判定方法在以A为根的DFS树中如果点u是割点并且点B位于u的某个子树中且该子树不经过u就无法回到A的祖先那么u就是A到B的必经点。这等价于在DFS过程中当遍历到u时检查其子节点v的子树中是否包含B。如果包含B且满足low[v] dfn[u]则u是必经点。实现步骤从A点开始进行DFS计算每个点的dfn和low。在DFS过程中维护一个状态记录B点是否已经被访问到。对于每个非根、非A/B的点u当检查其子节点v时如果发现low[v] dfn[u]并且B点位于以v为根的子树中这可以通过在DFS时记录每个节点的“子树范围”或通过一个标记数组来判定那么点u就是A到B的一个必经点。对于根节点A需要特殊判断如果A有两个或以上的子节点并且B位于其中一个子树中即B不是A的直接邻居这里需要仔细分析那么A本身也可能成为“必经点”但题目通常排除起点和终点。所以A点本身不参与计算。优点效率极高只需一次DFS。缺点算法理解难度大实现细节多容易写错。尤其是在判断“B是否在子树v中”这个条件时需要精巧的设计。对于竞赛而言如果时间紧张或者对Tarjan算法不熟我强烈推荐使用第一种朴素方法。它的逻辑简单在数据规模允许的情况下更可靠。接下来我将以第一种方法为例给出详细的代码实现和注释。4. 代码实现与逐行解析朴素DFS法我们采用C语言来实现使用邻接表存储图使用深度优先搜索DFS来判断连通性。#include iostream #include vector #include cstring using namespace std; const int MAXN 1005; // 根据题目最大规模设定 vectorint graph[MAXN]; // 邻接表 bool visited[MAXN]; int n, m, A, B; // 深度优先搜索判断从start出发能否到达target并避开点ban如果ban不为0 bool dfs(int start, int target, int ban) { if (start target) return true; // 已经到达终点 visited[start] true; for (int i 0; i graph[start].size(); i) { int next graph[start][i]; // 如果下一个点是禁止访问的点或者已经访问过则跳过 if (next ban || visited[next]) continue; if (dfs(next, target, ban)) return true; // 找到一条路径 } return false; // 从当前start出发的所有路径都尝试过了无法到达target } // 检查在禁止访问点ban的情况下A和B是否连通 bool isConnected(int ban) { memset(visited, false, sizeof(visited)); // 每次检查前重置访问标记 return dfs(A, B, ban); } int main() { cin n m; for (int i 0; i m; i) { int u, v; cin u v; graph[u].push_back(v); graph[v].push_back(u); // 无向图添加两条边 } cin A B; // 边界情况1首先检查A和B是否连通不禁止任何点 if (!isConnected(0)) { cout -1 endl; return 0; } int dangerousCount 0; // 枚举除A、B以外的所有点 for (int candidate 1; candidate n; candidate) { if (candidate A || candidate B) continue; // 禁止访问candidate点检查A和B是否仍然连通 if (!isConnected(candidate)) { dangerousCount; } } // 边界情况2如果没有任何危险点根据题目要求输出-1 if (dangerousCount 0) { cout -1 endl; } else { cout dangerousCount endl; } return 0; }代码关键点解析数据结构使用vectorint graph[MAXN]作为邻接表比邻接矩阵更节省空间遍历相邻点也更高效。DFS函数设计dfs(int start, int target, int ban)函数是核心。它尝试寻找从start到target的路径并避开编号为ban的点。这里采用递归实现逻辑清晰。如果找到一条路径立即返回true利用递归层层返回实现“短路”效果提高效率。连通性判断isConnected(int ban)函数封装了每次的判断逻辑。它首先清空visited数组然后调用dfs(A, B, ban)。这里ban0表示不禁止任何点因为顶点编号从1开始。主逻辑流程读入数据建图。首要检查调用isConnected(0)判断原始图中A和B是否连通。如果不连通直接输出-1并结束。这一步至关重要避免了后续无意义的枚举。枚举候选点从1到n遍历跳过A和B。对每个候选点candidate调用isConnected(candidate)。如果返回false说明该点是“危险”的计数器加一。输出结果如果计数器为0输出-1否则输出计数器的值。“删除”点的实现我们并没有真正地从邻接表中删除这个点及其所有边那样做非常低效。而是在DFS遍历时简单地“跳过”这个点if (next ban) continue;。这等价于在图中删除了该点但避免了修改图结构带来的开销。这个实现简洁明了在蓝桥杯的评测环境下通常能够获得满分。5. 常见“踩坑点”与优化讨论即便思路清晰在实现和调试时依然有几个地方容易出错。5.1 坑点一对“所有路径”的误解与算法正确性有同学可能会想DFS只能找到一条路径你怎么能根据“删除某点后DFS找不到路径”就断定该点是所有路径的必经点呢万一DFS走的路径恰好经过了该点而其他不经过该点的路径存在呢 这是一个非常好的问题。关键在于我们的DFS函数设计。上述代码中的dfs函数一旦找到一条路径就立即返回true。在判断isConnected(candidate)时我们关心的是“是否存在一条路径”。如果存在一条不经过candidate的路径那么isConnected(candidate)就会返回true。只有当所有从A到B的路径都经过candidate时禁止candidate后isConnected才会返回false。因为如果存在哪怕一条不经过它的路径我们的DFS就有可能找到它DFS会探索所有分支。所以这个算法是正确的。5.2 坑点二visited数组的初始化位置这是DFS写法中非常经典的错误。visited数组必须在每次调用isConnected即每次判断一个新的ban点时被重置为全false。如果忘记重置上一次搜索留下的访问标记会影响下一次搜索导致错误地认为图不连通。在我们的代码中memset(visited, false, sizeof(visited));语句放在了isConnected函数内部的开头这是正确的位置。5.3 坑点三图存储方式与遍历顺序我们使用了邻接表。如果使用邻接矩阵在稀疏图下会浪费大量空间并且遍历相邻节点时需要遍历整个一行效率低下。使用邻接表是更优选择。另外遍历邻接表时使用for (int next : graph[start])的C11范围for循环代码会更简洁。但在竞赛中确保编译器支持即可。5.4 性能优化讨论虽然O(N*(NM))的算法能过但我们也可以思考优化。记忆化/预处理我们进行了N-2次DFS每次都是独立的。能否共享一些信息例如我们可以从A点做一次DFS记录下到达每个点的所有可能路径信息但这在路径数量爆炸时不可行。转换为网络流问题可以把每个点拆成入点和出点中间连一条容量为1的边表示只能经过一次原图的边容量设为无穷大。然后求A到B的最大流。根据最大流最小割定理最大流的值就等于边不交的路径数这里是点不交通过拆点转化为边。如果最大流为1说明所有路径都共享某个点但求具体是哪些点比较麻烦。这不是本题的最优解。还是Tarjan最优雅高效的解法仍然是基于DFS树和dfn、low数组的Tarjan变种算法。如果数据量真的非常大这是唯一的选择。作为练习理解并实现这个算法对图论能力的提升很有帮助。5.5 关于输出-1的再讨论题目描述中“如果没有满足条件的点则输出-1”。什么情况下会没有满足条件的点A和B本身就不连通。我们已处理A和B连通但存在多条点不交的路径即点连通度大于1。例如A和B是一个环上的两个点那么删除环上任何一个其他点A和B仍然连通。此时危险点数为0应输出-1。A和B直接相连。这也属于上述情况的一种特例点连通度至少为2因为直连是一条路径可能还有其他路径。所以也输出-1。我们的代码逻辑完全覆盖了这些情况只要dangerousCount为0就输出-1。6. 测试用例设计与验证编写完代码一定要用多种情况的测试用例来验证。这里提供几个典型的测试用例用例1基本样例输入 7 6 1 2 1 3 2 4 3 4 4 5 5 6 5 7 1 6图结构1-2-4-5-6 和 1-3-4-5-6 是两条主要路径在4和5点交汇。 分析删除点4或点51和6之间仍然连通分别走另一条路。删除点2或点31和6也连通因为4和5还在。所以危险点数为0。 预期输出-1用例2存在唯一必经点输入 5 4 1 2 2 3 3 4 4 5 1 5图结构一条链 1-2-3-4-5。 分析删除2、3、4中任意一个1和5都不连通。所以危险点数为3。 预期输出3用例3起点终点不连通输入 4 2 1 2 3 4 1 4分析1和4之间没有路径。 预期输出-1用例4起点终点直连且有其他路径输入 4 4 1 2 1 4 2 3 3 4 1 4图结构1和4直连同时有1-2-3-4这条路径。 分析这是一个环删除任何中间点2或31和4仍可通过直连边连通。危险点数为0。 预期输出-1将我们的代码运行这些用例结果都应该符合预期。通过设计这些覆盖了连通、不连通、直连、多条路径、单一路径等情况的测试用例可以极大地增强对代码正确性的信心。这道“危险系数”题从问题抽象到算法选择再到实现细节和边界处理完整地走完了一遍解决图论应用问题的流程。它不像有些难题那样需要高深的算法模板但非常考验选手的基本功和对问题本质的洞察力。在竞赛中遇到这类题目稳住心态一步步完成“场景-模型-算法-实现-测试”的转换就能稳稳拿下。