信息学奥赛一本通 1522:网络 | OpenJudge 百练 1144:Network
【题目链接】
ybt 1522:网络
OpenJudge 百练 1144:Network
【题目考点】
1. 图论:割点
【解题思路】
每个交换机是一个顶点,如果两地点之间有电话线连接,那么两顶点之间有一条无向边,该图是无向图。
初始时任何地点之间都是可以通讯的,也就是说这是一个无向连通图。
如果一个交换机停止工作,导致其它一些地点不能通讯,这样的地点交灾区。那么也就是图中去掉该顶点后,有些顶点之间不再连通(没有路径),那么也就是整个图不再是连通图。这样的点就是割点。
灾区就是割点,统计灾区的数量就是统计割点的数量。
使用tarjan算法求出所有割点,将割点保存在一个set中,或用数组标记哪些顶点是割点,而后统计割点数量。
【题解代码】
解法1:Tarjan算法求割点,使用set保存割点
#include <bits/stdc++.h>
using namespace std;
#define N 105
int n, m;
vector<int> edge[N];//edge[i]:顶点i的邻接点
int dfn[N], low[N], ts, root;
set<int> cutVer;
void tarjan(int u)
{int child = 0;dfn[u] = low[u] = ++ts;for(int v : edge[u]){if(dfn[v] == 0){tarjan(v);low[u] = min(low[u], low[v]);if(u == root && ++child > 1 || u != root && dfn[u] <= low[v])cutVer.insert(u);}elselow[u] = min(low[u], dfn[v]);}
}
int main()
{int f, t;while(cin >> n && n != 0){ts = 0;//变量初始化 for(int i = 1; i <= n; ++i)edge[i].clear();memset(dfn, 0, sizeof(dfn));cutVer.clear();while(cin >> f && f != 0)while(cin.get() != '\n'){cin >> t;edge[f].push_back(t);edge[t].push_back(f);}for(int v = 1; v <= n; ++v) if(dfn[v] == 0)tarjan(root = v);cout << cutVer.size() << endl;}return 0;
}
解法2:Tarjan算法求割点,使用标记数组保存割点
#include <bits/stdc++.h>
using namespace std;
#define N 105
int n, dfn[N], low[N], ts, root, ct;
vector<int> edge[N];
bool cutVer[N];//cutVer[i]:i是否是割点
void tarjan(int u)
{int child = 0;dfn[u] = low[u] = ++ts;for(int v : edge[u]){if(dfn[v] == 0){tarjan(v);low[u] = min(low[u], low[v]);if(u == root && ++child > 1 || u != root && dfn[u] <= low[v])cutVer[u] = true;//u是割点 }elselow[u] = min(low[u], dfn[v]); }
}
int main()
{int f, t;while(cin >> n && n != 0){ts = ct = 0;//变量初始化 for(int i = 1; i <= n; ++i)edge[i].clear();memset(cutVer, 0, sizeof(cutVer));memset(dfn, 0, sizeof(dfn));while(cin >> f && f != 0)while(cin.get() != '\n'){cin >> t;edge[f].push_back(t);edge[t].push_back(f);}for(int v = 1; v <= n; ++v) if(dfn[v] == 0)tarjan(root = v);for(int v = 1; v <= n; ++v) if(cutVer[v])//统计割点数量 ct++;cout << ct << endl;}return 0;
}
相关文章:
信息学奥赛一本通 1522:网络 | OpenJudge 百练 1144:Network
【题目链接】 ybt 1522:网络 OpenJudge 百练 1144:Network 【题目考点】 1. 图论:割点 【解题思路】 每个交换机是一个顶点,如果两地点之间有电话线连接,那么两顶点之间有一条无向边,该图是无向图。 初始时任何地…...
本地部署DeepSeek的硬件配置建议
本地部署DeepSeek的硬件配置需求因模型参数规模和部署工具不同而有所差异,以下是综合多个来源的详细要求: 1. 基础配置(适用于7B参数模型) 内存:最低8GB,推荐16GB及以上;若使用Ollama工具&…...
Redis面试题----Redis 的持久化机制是什么?各自的优缺点?
Redis 提供了两种主要的持久化机制,分别是 RDB(Redis Database)和 AOF(Append Only File),下面将详细介绍它们的原理、优缺点。 RDB(Redis Database) 原理 RDB 持久化是将 Redis 在某个时间点上的数据集快照以二进制文件的形式保存到磁盘上。可以通过手动执行 SAVE …...
C#实现本地AI聊天功能(Deepseek R1及其他模型)。
前言 1、C#实现本地AI聊天功能 WPFOllamaSharpe实现本地聊天功能,可以选择使用Deepseek 及其他模型。 2、此程序默认你已经安装好了Ollama。 在运行前需要线安装好Ollama,如何安装请自行搜索 Ollama下载地址: https://ollama.org.cn Ollama模型下载地址…...
Metal 学习笔记四:顶点函数
到目前为止,您已经完成了 3D 模型和图形管道。现在,是时候看看 Metal 中两个可编程阶段中的第一个阶段,即顶点阶段,更具体地说,是顶点函数。 着色器函数 定义着色器函数时,可以为其指定一个属性。您将在本…...
C# string转unicode字符
在 C# 中,将字符串转换为 Unicode 字符(即每个字符的 Unicode 码点)可以通过遍历字符串中的每个字符并获取其 Unicode 值来实现。Unicode 值是一个整数,表示字符在 Unicode 标准中的唯一编号。 以下是实现方法: 1. 获…...
HITCON2017SSRFME-学习复盘
代码审计 192.168.122.15 <?phpif (isset($_SERVER[HTTP_X_FORWARDED_FOR])) {$http_x_headers explode(,, $_SERVER[HTTP_X_FORWARDED_FOR]);//用逗号分割多个IP$_SERVER[REMOTE_ADDR] $http_x_headers[0];}echo $_SERVER["REMOTE_ADDR"];//给第一个IP发送请…...
【Http和Https区别】
概念: 一、Http协议 HTTP(超文本传输协议)是一种用于传输超媒体文档(如HTML)的应用层协议,主要用于Web浏览器和服务器之间的通信。http也是客户端和服务器之间请求与响应的标准协议,客户端通常…...
2025数学建模竞赛汇总,错过再等一年
01、2025第十届数维杯大学生数学建模挑战赛(小国赛) 竞赛介绍:数学建模行业内仅次于国赛和美赛的的第三赛事,被多所高校认定为国家级二类竞赛。赛题类型是国内唯一和高教社杯国赛题型风格完全一致的全国性数学建模竞赛࿰…...
基于SSM的《计算机网络》题库管理系统(源码+lw+部署文档+讲解),源码可白嫖!
摘 要 《计算机网络》题库管理系统是一种新颖的考试管理模式,因为系统是用Java技术进行开发。系统分为三个用户进行登录并操作,分别是管理员、教师和学生。教师在系统后台新增试题和试卷,学生进行在线考试,还能对考生记录、错题…...
ReentrantLock 用法与源码剖析笔记
📒 ReentrantLock 用法与源码剖析笔记 🚀 一、ReentrantLock 核心特性 🔄 可重入性:同一线程可重复获取锁(最大递归次数为 Integer.MAX_VALUE)🔧 公平性:支持公平锁(按等…...
矩阵的 正定(Positive Definite)与负定(Negative Definite):从Fisher信息矩阵看“曲率”的秘密
矩阵的正定与负定:从Fisher信息矩阵看“曲率”的秘密 在数学和统计学中,矩阵的“正定性”和“负定性”是一对重要概念,尤其在优化、统计推断和机器学习中频繁出现。比如,Fisher信息矩阵(Fisher Information Matrix, F…...
被裁20240927 --- WSL-Ubuntu20.04安装cuda、cuDNN、tensorRT
cuda、cuDNN、tensorRT的使用场景 1. CUDA(Compute Unified Device Architecture) 作用: GPU 通用计算:CUDA 是 NVIDIA 的并行计算平台和编程模型,允许开发者直接利用 GPU 的并行计算能力,加速通用计算任…...
uniapp写的h5跳转小程序
使用场景: 我们对接第三方支付的时候,对方只提供了原生小程序id和appid,由我们的app和h5平台跳转至小程序。 遇到的问题: app跳转本地正常,线上报错如下 解决办法: 需要去微信开放平台申请应用appid 易…...
[SWPUCTF 2022 新生赛]ez_rce
打开题目就在线环境,发现只有一句话:真的什么都没有吗 F12查看控制台和源代码也没发现任何信息,然后用虚拟机里面的dirsearch扫一下这个网站就能得到: 然后这里扫出来的结果查看的直接就是robots.txt,然后就能看到: …...
递归、搜索与回溯算法 —— 名词解析
目录 一、递归 1、什么是递归? 2、递归的数学类比 3、为什么要用到递归? 问题具有递归结构: 代码简洁易懂: 解决复杂问题: 处理嵌套结构: 4、如何理解递归? 明确基准条件: …...
【docker】docker swarm lock和unlock的区别,以及旧节点重启的隐患
docker swarm lock/unlock 的作用 Docker Swarm 提供了**加密集群状态(Encrypted Raft logs)**的功能,可以防止 Swarm 集群的管理数据(如任务分配、集群配置等)在磁盘上被未授权访问。 docker swarm lock:…...
Grafana使用日志5--如何重置Grafana密码
背景 有时候当账号太多的时候,根本记不住所有的账号密码,这时候就很容易登录失败,这时候怎么办呢? 接下来就让我来给大家演示一下Grafana的账号如果忘记了的话,该怎么找回自己的账号密码 操作 让我们来看一下具体的…...
ELK搭建初入
ELK搭建: 1、安装ElasticSearch (用于存储收集到的日志信息) 解压安装包 tar -xzvf elasticsearch-8.17.2-linux-x86_64.tar.gz 启动es:bin/elasticsearch –d(默认端口号9200) 浏览器输入es地址。出现…...
JVM 高级面试题及答案整理,最新面试题
JVM中的垃圾收集器有哪些,它们的工作原理是什么? JVM中的垃圾收集器主要包括以下几种: 1、 Serial收集器:它是一个单线程收集器,工作时会暂停所有其他工作线程("Stop-The-World")&a…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
