2013年蓝桥杯国赛C组危险系数(洛谷P8604):图论算法解密

深度学习
• 阅读 15

2013年蓝桥杯国赛C组危险系数(洛谷P8604):图论算法解密

一、问题描述

地下网络由多个站点和连接通道组成。当某个站点被敌人破坏后,可能导致其他站点间失去联系。危险系数DF(x,y)定义为:使站点x和y断开连接的所有关键点z的数量。

二、算法核心思想

  1. 表示:使用邻接表存储网络结构
  2. 连通性检查BFS广度优先搜索算法
  3. 关键点判定:逐个排除节点后检查连通性

三、实现步骤

  1. 输入处理:读取站点数n、通道数m及所有通道
  2. 初始连通性检查:确保x和y初始连通
  3. 关键点检测
    • 遍历所有非x/y的站点z
    • 暂时移除z后检查x和y的连通性
    • 统计导致不连通的z的数量
  4. 结果输出:返回危险系数或-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;
}

五、优化思路

  1. 提前终止:发现不连通立即返回
  2. 并行处理:可并行检查不同z的情况
  3. 更高效算法:可以考虑使用割点算法优化

六、学习要点

  1. 图的表示方法(邻接表/邻接矩阵
  2. BFS算法的应用
  3. 关键节点识别技巧
  4. 算法效率优化思路

转自:2013年蓝桥杯国赛C组危险系数(洛谷P8604):图论算法解密

点赞
收藏
评论区
推荐文章
Souleigh ✨ Souleigh ✨
4年前
【C 陷阱与缺陷 学习笔记】(一)词法陷阱
一内容0\.不同于当程序员本意是作比较运算时,却可能无意中误写成了赋值运算。1.本意是检查x与y是否相等:cif(xy)break;实际上是将y的值赋值给了x,然后再检查该值是否为0。2.本意是跳过文件中的空白字符:cwhile(c''||c'\t'||
Patrick Patrick
4年前
【分治法】解决中位数问题、格雷码问题以及分治法直接折半存在的问题讨论————武汉理工大学算法分析实验1
AlgorithmExperiment算法分析课实验分治法的核心思想是将问题分为若干子问题去,使规模一步步缩小,最终分到一步就能得出结果。要注意每个子问题需要性质相同而且相互不重复。采用分治法完成如下任务:i.中位数问题问题描述设X0:n1和Y0:n–1为两个数组,每个数组中含有n个已排好序的数。找出X和Y
可莉 可莉
3年前
12.21 php
12.21phpfpm的pool为了避免因多站点使用同一个pool时因一个站点故障导致pool出问题,进而影响使用同一个pool的其他站点的正常运行,要对每个站点配置一个单独的pool。为phpfpm增加poolroot@cham002cham.comcd/usr/local
Wesley13 Wesley13
3年前
FLV文件格式
1.        FLV文件对齐方式FLV文件以大端对齐方式存放多字节整型。如存放数字无符号16位的数字300(0x012C),那么在FLV文件中存放的顺序是:|0x01|0x2C|。如果是无符号32位数字300(0x0000012C),那么在FLV文件中的存放顺序是:|0x00|0x00|0x00|0x01|0x2C。2.  
Stella981 Stella981
3年前
IdentityServer4环境部署失败分析贴(一)
前言:在部署Idv4站点和其客户端在外网时,发现了许多问题,折腾了许久,翻看了许多代码,写个MD记录一下。1.受保护站点提示错误:Unabletoobtainconfigurationfrom:'\PIIishidden\'.fail:Microsoft.AspNetCore.Server.Kes
Wesley13 Wesley13
3年前
oracle多表查询之经典面试题
一、笛卡尔积1.概念笛卡尔乘积是指在数学中,两个集合_X_和_Y_的笛卡尓积(Cartesianproduct),又称直积,表示为_X_×_Y_,第一个对象是_X_的成员而第二个对象是_Y_的所有可能有序对的其中一个成员。\1\简单点说就是:集合X的每个元素和集合B的每个元素进行两两组合,组合次数等于集合X元素数量
Wesley13 Wesley13
3年前
PHP字符串函数
<?php$x10;$x$x;echo$x;//输出10$c10;$c$c;echo$c;//输出10$y10;$y$y;echo$y;//输出10$z10;$z
Wesley13 Wesley13
3年前
Java多线程导致的的一个事物性问题
业务场景我们现在有一个类似于文件上传的功能,各个子站点接受业务,业务上传文件,各个子站点的文件需要提交到总站点保存,文件是按批次提交到总站点的,也就是说,一个批次下面约有几百个文件。      考虑到白天提交这么多文件会影响到子站点其他系统带宽,我们将分站点的文件提交到总站点这个操作过程独立出来,放到晚上来做,具体时间是晚上7:00到早上7:00。
一次MTU问题导致的RDS访问故障
导语VPN是一种通过公网连接两个或多个私网站点的专用网络,使得这些站点仿佛是通过专线连接在一起。IPSec是一套协议框架,用于保证数据传输的私密性,完整性,真实性。但是VPN网络经常会带来一些连通性上的问题,通常与MTU设置的不合理
深度学习 深度学习
1星期前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,