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

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

6小时前

蓝桥杯2013国赛C组危险系数(洛谷8604):基于BFS算法的图论题解 蓝桥杯国赛 图论算法 BFS搜索 蓝桥杯比赛 蓝桥杯 广搜 广度优先搜索 无向图 第1张

一、题目解读

题目背景源自抗日战争时期的冀中平原地道战,站点间通过通道形成网络。危险系数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;
}

五、总结

该解法通过BFS的简洁性与高效性,将复杂的路径分析转化为逐点连通性判断。关键在于识别“关键点”为割点时,必须确保删除该节点后原路径中断。用户代码巧妙利用BFS避免递归开销,适用于大规模图数据。在竞赛中,此类算法优化能有效提升解题效率,是图论问题的典型解题思路。

原创内容 转载请注明出处

分享给朋友:

相关文章

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

一、题目解读2024年蓝桥杯省B组“传送阵”题目要求处理一个包含n个节点的图,节点间存在单向传输关系。每个节点i可传送至a[i]指定的节点,形成可能存在的环结构。题目需求解从任意节点出发能到达的最长路...

【蓝桥杯国赛A组】冰山体积计算:动态规划与map统计的解题方案(洛谷P8767)

【蓝桥杯国赛A组】冰山体积计算:动态规划与map统计的解题方案(洛谷P8767)

一、题目解读本题为2021年蓝桥杯国赛A组题目“冰山”(洛谷P8767),要求处理冰山在融化与新生成过程中的体积变化。每日存在两种操作:冰山体积按固定值x融化(体积不足x的部分视为完全融化),以及新增...

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

一、题目解读力扣3112题要求解决带时间限制的最短路径问题:给定一个有向图,节点具有消失时间,需计算从起点到各节点的最短路径,且路径总时间不能超过节点的消失时间。题目难点在于需在传统最短路径算法(如D...

洛谷1363题解法:虚拟坐标优化BFS解决循环迷宫问题(附代码详解)

洛谷1363题解法:虚拟坐标优化BFS解决循环迷宫问题(附代码详解)

一、题目解读洛谷1363题要求判断在给定大小的循环迷宫中,从起点出发是否可以通过移动到达多个不同的路径方向。迷宫由字符矩阵表示,'S'为起点,'#'为障碍物,其余为可通...

【力扣2846题】图论+二进制提升:高效解决连通性问题(附C++代码)

【力扣2846题】图论+二进制提升:高效解决连通性问题(附C++代码)

一、题目解读力扣2846题要求解决一个基于图连通性的操作优化问题。给定一个无向图,包含边权重,以及一系列查询,每个查询询问两点间路径的最小操作次数。题目关键在于高效计算路径上权重分布的统计信息,并转化...

洛谷P3393题解:基于多源BFS与Dijkstra算法求解图论最小花费路径问题

洛谷P3393题解:基于多源BFS与Dijkstra算法求解图论最小花费路径问题

一、题目解读洛谷P3393题要求在一个包含N个城市和M条双向道路的图中,求解从起点1到终点N的最小花费路径。图中存在僵尸城市(僵尸无法通过)和危险城市(由僵尸城市扩散S步后标记),需要避开所有危险城市...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。