当前位置：首页 > 蓝桥杯 > 蓝桥杯2013国赛C组危险系数（洛谷8604）：基于BFS算法的图论题解

蓝桥杯2013国赛C组危险系数（洛谷8604）：基于BFS算法的图论题解

2个月前 (08-29)

一、题目解读

题目背景源自抗日战争时期的冀中平原地道战，站点间通过通道形成网络。危险系数DF(x,y)定义为：若破坏站点z导致x与y不连通，则z为关键点，DF(x,y)即关键点数量。任务是根据网络结构求两站点间的危险系数，不连通时输出-1。题目本质是图论中的割点问题，需通过路径分析找到关键节点。

二、解题思路

用户采用BFS（广度优先搜索）算法解决。核心思想是：

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;
}