蓝桥杯2013国赛C组危险系数(洛谷8604):基于BFS算法的图论题解
一、题目解读
题目背景源自抗日战争时期的冀中平原地道战,站点间通过通道形成网络。危险系数DF(x,y)定义为:若破坏站点z导致x与y不连通,则z为关键点,DF(x,y)即关键点数量。任务是根据网络结构求两站点间的危险系数,不连通时输出-1。题目本质是图论中的割点问题,需通过路径分析找到关键节点。
二、解题思路
2. 通过BFS遍历检查从x到y的连通性,忽略指定节点(关键点候选),若断开则计数。
3. 遍历所有节点作为忽略对象,统计关键点数量。
该解法利用BFS的逐层扩展特性,快速判断节点删除后的连通状态,避免复杂路径搜索。
三、解题步骤
1. 数据输入与图构建
读入n(站点数)、m(边数),构建邻接表graph(vector存储双向边)。
2. 连通性检查
定义isConnected函数:
初始化visited数组,标记忽略节点。
从起点x开始BFS,若到达终点y则返回true,否则遍历所有可达节点。
3. 关键点统计
遍历每个节点z(非x/y),调用isConnected(x,y,z),若返回false则z为关键点,计数。
4. 输出结果
若初始x与y不连通,输出-1;否则输出关键点数量。
四、代码及注释
#include <iostream> #include <vector> #include <queue> using namespace std; const int MAXN = 1005; vector<int> graph[MAXN]; // 邻接表存储图 bool visited[MAXN]; // BFS检查从u到v是否连通,忽略节点ignore bool isConnected(int u, int v, int ignore, int n) { fill(visited, visited + n + 1, false); queue<int> q; q.push(u); visited[u] = true; visited[ignore] = true; // 标记忽略的节点为已访问 while (!q.empty()) { int current = q.front(); q.pop(); for (int neighbor : graph[current]) { if (!visited[neighbor]) { if (neighbor == v) return true; visited[neighbor] = true; q.push(neighbor); } } } return false; } int main() { int n, m; 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); } int x, y; cin >> x >> y; // 首先检查初始连通性 if (!isConnected(x, y, -1, n)) { cout << -1 << endl; return 0; } int count = 0; // 检查每个可能的z for (int z = 1; z <= n; z++) { if (z == x || z == y) continue; // 跳过x和y本身 if (!isConnected(x, y, z, n)) { count++; } } cout << count << endl; return 0; }
五、总结
该解法通过BFS的简洁性与高效性,将复杂的路径分析转化为逐点连通性判断。关键在于识别“关键点”为割点时,必须确保删除该节点后原路径中断。用户代码巧妙利用BFS避免递归开销,适用于大规模图数据。在竞赛中,此类算法优化能有效提升解题效率,是图论问题的典型解题思路。
原创内容 转载请注明出处