tarjan算法——割边
今天也是小小的学了一个tarjan算法中的割边的一个应用
他和割点很像，都是用来处理无向图的，只不过是不能走反向边罢了
我们首先来说一个割边的定义
割边
当我们在无向图中删除一个边，无向图被分成不联通的两部分，那么这条边就是割边
我们来看一下割边的模版代码的注释
1.变量名和数组
vector<pair<int,int>> edge;//边集
vector<int> e[200005];//每个点的出边集
int dfn[200005];//每个点的深搜序标记
int low[200005];//每个点的回溯值
int len;
vector<pair<int,int>> brige;//统计割边的数组2.加边函数代码
void add(int v,int u)
{edge.push_back({v,u});e[v].push_back(edge.size()-1);//边的序号是从0开始，可以通过异或1查看是否是反边
}3.tarjan函数代码
void tarjan(int v,int from)//from表示边来源的序号
{dfn[v]=low[v]=++len;//给每个点打上标记for(int xu:e[v])//去寻找当前点出边的序号{int u=edge[xu].second;//寻找当前点的子节点if(dfn[u]==0)//如果没有访问过{tarjan(u,xu);low[v]=min(low[v],low[u]);if(low[u]>dfn[v])//是割边{brige.push_back({v,u});}}else if(xu!=(from^1))//查询过并且不是反边{low[v]=min(low[v],dfn[u]);}}
}例题
T103481 【模板】割边
思路：割边的板题，直接写就OK了，用上面的板子即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int u,v;
vector<pair<int,int>> edge;//边集
vector<int> e[200005];//每个点的出边集
int dfn[200005];
int low[200005];
int len;
vector<pair<int,int>> brige;
int cnt;
void add(int v,int u)
{edge.push_back({v,u});e[v].push_back(edge.size()-1);
}
void tarjan(int v,int from)//from表示边来源的序号
{dfn[v]=low[v]=++len;for(int xu:e[v]){int u=edge[xu].second;if(dfn[u]==0){tarjan(u,xu);low[v]=min(low[v],low[u]);if(low[u]>dfn[v]){brige.push_back({v,u});}}else if(xu!=(from^1)){low[v]=min(low[v],dfn[u]);}}
}
signed main()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>u>>v;add(u,v);add(v,u);}for(int i=1;i<=n;i++){if(dfn[i]==0)tarjan(i,-1);}cout<<brige.size();return 0;
}P1656 炸铁路
思路：也是割边的模版题，只不过需要对其进行排序即可，反正用的也是pair直接排序就好了，不需要重载
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int u,v;
vector<pair<int,int>> edge;
vector<int> e[200005];
int dfn[200005];
int low[200005];
int len;
vector<pair<int,int>> brige;
void add(int v,int u)
{edge.push_back({v,u});e[v].push_back(edge.size()-1);
}
void tarjan(int v,int from)
{dfn[v]=low[v]=++len;for(int xu:e[v]){int u=edge[xu].second;if(dfn[u]==0){tarjan(u,xu);low[v]=min(low[v],low[u]);if(low[u]>dfn[v]){brige.push_back({v,u});}}else if(xu!=(from^1)){low[v]=min(low[v],dfn[u]);}}
}
signed main()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>u>>v;add(u,v);add(v,u);}for(int i=1;i<=n;i++){if(dfn[i]==0)tarjan(i,-1);}sort(brige.begin(),brige.end());for(auto u:brige){cout<<u.first<<" "<<u.second<<"\n";}return 0;
}P7687 [CEOI2005] Critical Network Lines
思路：唯一不同的地方就是要去维护一个子树内的a的网络的数量或者b网络的数量，并且所有关键路径一定都是割边，我们只需要找到割边里面的满足子节点里面包括a的数量是0或者k，b的数量为0或者l的即可
#include<bits/stdc++.h>
using namespace std; const int MAXN = 100005;
struct Node { int dfn, low, suma, sumb;
}; int n, m, k, l;
int u, v;
vector<pair<int, int>> edge;
vector<int> e[MAXN];
vector<pair<int, int>> bridge;
Node nodes[MAXN];
int len; void addEdge(int v, int u) { edge.emplace_back(v, u); e[v].push_back(edge.size() - 1);
} void tarjan(int v, int from) { nodes[v].dfn = nodes[v].low = ++len; for (auto xu : e[v]) { int u = edge[xu].second; if (nodes[u].dfn == 0) { tarjan(u, xu); nodes[v].low = min(nodes[v].low, nodes[u].low); nodes[v].suma += nodes[u].suma; nodes[v].sumb += nodes[u].sumb; if (nodes[u].low > nodes[v].dfn && ((nodes[u].suma == 0 || nodes[u].sumb == 0) || (nodes[u].suma == k || nodes[u].sumb == l))) { bridge.emplace_back(v, u); } } else if (xu != (from ^ 1)) { nodes[v].low = min(nodes[v].low, nodes[u].dfn); } }
} signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> k >> l; for (int i = 1; i <= k; i++) { cin >> u; nodes[u].suma = 1; // 关键节点的计数 } for (int i = 1; i <= l; i++) { cin >> u; nodes[u].sumb = 1; // 另外一类关键节点的计数 } for (int i = 1; i <= m; i++) { cin >> u >> v; addEdge(u, v); addEdge(v, u); } for (int i = 1; i <= n; i++) { if (nodes[i].dfn == 0) { tarjan(i, -1); } } cout << bridge.size() << "\n"; for (const auto& br : bridge) { cout << br.first << " " << br.second << "\n"; } return 0;
}相关文章：
tarjan算法——割边
今天也是小小的学了一个tarjan算法中的割边的一个应用 他和割点很像，都是用来处理无向图的，只不过是不能走反向边罢了 我们首先来说一个割边的定义 割边 当我们在无向图中删除一个边，无向图被分成不联通的两部分，那么这条边就…...
ESP32 I2S音频总线学习笔记（一）：初识I2S通信与配置基础
文章目录 简介为什么需要I2S？关于音频信号采样率分辨率音频声道 怎样使用I2S传输音频？位时钟BCLK字时钟WS串行数据SD I2S传输模型I2S通信格式I2S格式左对齐格式右对齐格式 i2s基本配置i2s 底层API加载I2S驱动设置I2S使用的引脚I2S读取数据I2S发送数据卸载…...
Mybatisplus-IService
IService 是 MyBatis-Plus 提供的一个通用 Service 层接口，它封装了常见的 CRUD 操作，包括插入、删除、查询和分页等。通过继承 IService 接口，可以快速实现对数据库的基本操作，同时保持代码的简洁性和可维护性。 IService 接口中…...
深入浅出 Beam Search：自然语言处理中的高效搜索利器
Beam Search 技术详解 1. 引言 Beam Search 是一种广泛应用于自然语言处理（NLP）、机器翻译、语音识别等序列生成任务中的启发式搜索方法。本文将详细探讨 Beam Search 的原理、实现步骤、应用场景及其优缺点，并通过具体例子帮助读者更好地理…...
MySQL 可重复读隔离级别，完全解决幻读了吗？
什么是事务隔离级别？ 事务隔离级别是数据库用来控制多个并发事务之间如何交互的机制。不同的隔离级别提供了不同程度的保护，以防止并发事务之间的相互干扰。MySQL 支持四种隔离级别： 读未提交（Read Uncommitted）&…...
Nginx知识详解（理论+实战更易懂）
目录 一、Nginx架构和安装 1.1 Nginx 概述 1.1.1 nginx介绍 1.1.2?Nginx 功能介绍 1.1.3?基础特性 1.1.4?Web 服务相关的功能 1.2?Nginx 架构和进程 1.2.1?Nginx 进程结构 1.2.2?Nginx 进程间通信 1.2.3?Nginx 启动和 HTTP 连接建立 1.2.4?HTTP 处理过程 1…...
VScode怎么重启
原文链接：【vscode】vscode重新启动 键盘按下 Ctrl Shift p 打开命令行，如下图： 输入Reload Window，如下图：...
华夏ERP系统部署
JDK安装及环境变量配置 数据库安装 Redis安装部署 Nginx安装部署 后端程序前端程序部署...
实际部署Dify可能遇到的问题：忘记密码、开启HTTPS、知识库文档上传的大小限制和数量限制
背景 前面我们以 docker compose 容器化的方式本地部署了 Dify 社区版，并快速体验了其聊天助手、工作量编排以及智能体（Agent）功能。不过后续实际生产环境使用时遇到了忘记密码、如何开启SSL以支持HTTPS、如何突破知识库文档上传的大小限制和…...
：内存分配函数[4]--free)
【C语言】库函数常见的陷阱与缺陷(三)：内存分配函数[4]--free
C语言中的free函数用于释放之前通过malloc、calloc或realloc动态分配的内存。然而，在使用free函数时，开发者可能会遇到一些陷阱和缺陷。 一、功能与用法 free 函数是 C 语言中用于释放动态分配内存的关键函数。在程序使用 malloc、calloc 或 realloc 等函数在堆上分配了内存…...
【TypeScript篇】TypeScript命令行编译和自动化编译
目录 1. 命令行编译 步骤一：创建一个demo.ts文件 步骤二：全局安装TypeScript 步骤三：使用命令编译.ts文件 2. 自动化编译 步骤一：生成编译控制文件 步骤二：开启监视 3. 自动化编译的一些其它问题 1. 命令行编译…...
电子应用设计方案78：智能窗户系统设计
智能窗户系统设计 一、引言 智能窗户系统旨在为用户提供更便捷、舒适和节能的窗户控制体验，同时增强家居的安全性和智能化程度。 二、系统概述 1. 系统目标 - 实现窗户的自动开关控制，根据环境条件和用户设定进行操作。 - 具备风雨感应功能，…...
数据挖掘笔记 | 插值 | 拉格朗日插值 | 龙格现象 | 埃尔米特插值 | 分段三次埃尔米特插值
Interpolation插值 对于缺失值的处理，比较常见的是数值分析中的插值和拟合这两种方法。插值指的是在离散数据的基础上补插连续函数，使得这条连续曲线通过全部给定的离散数据点；拟合则是找到一条“最优”的曲线，尽可能地贴近平…...
)
Ubuntu网络配置(桥接模式, nat模式, host主机模式)
windows上安装了vmware虚拟机， vmware虚拟机上运行着ubuntu系统。windows与虚拟机可以通过三种方式进行通信。分别是桥接模式；nat模式；host模式 一、桥接模式 所谓桥接模式，也就是虚拟机与宿主机处于同一个网段， 宿主机…...
【Linux网络编程】第十七弹---深入理解以太网与ARP协议：从帧格式到数据报解析
✨个人主页： 熬夜学编程的小林 💗系列专栏： 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【Linux网络编程】 目录 1、认识以太网 1.1、以太网帧格式 1.2、认识 MAC 地址 1.3、对比理解 MAC 地址和 IP 地址 1.4、认识 MT…...
AVL 树
1.AVL树的概念 AVL树是最先发明的自平衡二叉查找树，AVL树可以是一棵空树，或者具有以下性质的树：左右子树都是AVL树。且左右子树的高度差的绝对值不超过1。 AVL树是一颗高度平衡搜索二叉树，通过控制高度去控制平衡。 AVL树的发明…...
PHP关键字Self、Static和parent的区别
简介 在使用PHP代码时，您可能经常会遇到parent::、static::和self::。但是当你第一次作为一个开发人员开始的时候，有时候你会很困惑，不知道它们是做什么的，以及它们之间的区别。 在我第一次作为开发人员开始工作后的很长一段时间…...
Vscode左大括号不另起一行、注释自动换行
参考大佬的博客VSCode 格式化 cpp 文件时配置左大括号不换行_vscode大括号不换行-CSDN博客 Clang_format_style {BasedOnStyle: Chromium, IndentWidth: 4}...
golang标准库archive/tar实现打包压缩及解压
文章目录 前言一、单个文件操作1.单个文件打包示例2.单个文件解包示例 二、目录示例1.打包压缩2.解包 补充 前言 这个包就是将文件进行打包和解包，通俗理解就是Linux 下的 tar 命令。 主要是通过 tar.Reader 读取 tar 包，通过 tar.Writer 写入 tar包&am…...
模方匀色功能中，加载的模板文件从哪里来
使用 DasViewerV3.1.2及以上版本导出的颜色调整文件 模方是一款针对实景三维模型的冗余碎片、水面残缺、道路不平、标牌破损、纹理拉伸模糊等共性问题研发的实景三维模型修复编辑软件。模方4.2新增内置“自动UV展开”功能，新增局部调色功能和DOM匀色功能等。同时可与…...
maya 删除 Ctrl + Delete vs Delete
在 Autodesk Maya 中删除选定顶点的步骤： 1. 选择顶点： 进入顶点选择模式： 按 F9 键（切换到顶点选择模式）。 或者，在工具栏中点击顶点选择图标（顶点模式）。 在视图中选择您想要删…...
为何String不可变，String的运算符重载
1.为何String不可变 java9之前，String的源码中是用字符数组实现的，同时使用了final和private修饰，被final修饰的结果就是变量不可修改、类不可继承、方法不可重写，被private修饰就无法对外暴露，这就是为何String不可变…...
WebRTC ：原理、协议和应用场景
WebRTC（Web Real-Time Communication）是一种用于在Web浏览器和移动应用程序之间进行实时通信的开放标准。它通过将音频、视频和数据传输集成到Web浏览器中，使得实时通信变得简单且无需任何插件或第三方软件。 一、WebRTC 的原理 WebRTC的实…...
Windows FTP服务器搭建指南
在Windows上搭建FTP服务器可以通过以下步骤完成。这里以Windows 10为例，使用系统自带的IIS（Internet Information Services）来搭建FTP服务器。 步骤1：安装IIS和FTP服务器组件 打开“控制面板”： 按 Win R，…...
DP协议：Link层（二）
书接上文，内容多了难免会有一种知识点零碎感，但是坚持学下去，有一天你会发现已经不知不觉可以链接成一张知识网络了。 AUX提供的services 前面咱刚刚简单的认识了AUX CH的状态和仲裁，这次咱们接着聊聊AUX提供的services。 管理连接和设备：AUX CH就像是一个管家，负责找到…...
HAL 库 HAL_UARTEx_ReceiveToIdle_IT 函数解析
一、存在位置：stm32f1xx_hal_uart.c 二、具体代码 二、返回值：HAL_StatusTypeDef 通过查看返回值HAL_StatusTypeDef在stm32f1xx_hal_edf.h文件中定义为结构体类型。 status：（进展的）状况，情形 三、函数名…...
C++ 设计模式：职责链模式（Chain of Responsibility）
链接：C 设计模式 链接：C 设计模式 - 组合模式 职责链模式（Chain of Responsibility Pattern）是一种行为型设计模式，它允许多个对象都有机会处理请求，从而避免请求的发送者和接收者之间的耦合。这些对象通过…...
数据库约束和查询
一 约束意义 这个后面的字段是什么意思呢? 先前说数据类型是一种约束，约束我们只能放该类型的数据，还有其它的约束来保证数据的合法性，下面的字段就和约束有关。 编译器的编译就是一个约束，保证我们的代码一定是语法合格的。我们…...
【文献精读笔记】Explainability for Large Language Models: A Survey （大语言模型的可解释性综述）（二）
****非斜体正文为原文献内容（也包含笔者的补充），灰色块中是对文章细节的进一步详细解释！ 3.1.2 基于注意力的解释（Attention-Based Explanation） 注意力机制可以揭示输入数据中各个部分之间的关系&#…...
AI大模型-提示工程学笔记1
卷首语：我所知的是我自己非常无知，所以我要不断学习。 写给AI入行比较晚的小白们（比如我自己）看的，大神可以直接路过无视了。 几个基本概念 1. 给LLM提示 用户可以通过简单的提示词（Prompts）…...
webrtc-internals调试工具
Google 的 Chrome（87 或更高版本）WebRTC 内部工具是一套内置于 Chrome 浏览器中的调试工具; webrtc-internals 能够查看有关视频和音频轨道、使用的编解码器以及流的一般质量的详细信息。这些知识对于解决音频和视频质量差的问题非常有帮助。 webrtc-int…...
百度PaddleSpeech识别大音频文件报错
一、背景 公司前同事留下了一套语音识别项目，内部使用百度PaddleSpeech。在项目验收的时候发现无法识别大音频文件，但是可以识别小音频文件。 这套项目是通过python调用的百度PaddleSpeech，然后提供了restful接口，然后java项目可…...
)
No.3十六届蓝桥杯备战|数据类型长度|sizeof|typedef|练习(C++)
数据类型⻓度 每⼀种数据类型都有⾃⼰的⻓度，使⽤不同的数据类型，能够创建出⻓度不同的变量，变量⻓度的不同，存储的数据范围就有所差异。 sizeof操作符 sizeof 是⼀个关键字，也是操作符，专⻔是⽤来计算特…...
MapReduce相关概念（自用）
MapReduce：分布式计算模型 MapReduce 是一种分布式计算模型，由 Google 在 2004 年提出，用于大规模数据集（TB 或 PB 级别）的分布式处理。它通过简单的编程模型，将复杂的分布式计算分解为两个基本阶段&#…...
)
Nginx - 整合lua 实现对POST请求的参数拦截校验(不使用Openresty)
文章目录 概述步骤 1: 安装 Nginx 和 Lua 模块步骤 2: 创建 Lua 脚本用于参数校验步骤 3: 配置 Nginx 使用 Lua 脚本写法二： 状态码写法三 ： 返回自定义JSON复杂的正则校验 步骤 4: 测试和验证ngx.HTTP_* 枚举值 概述 一个不使用 OpenResty 的 Nginx 集…...
I2C（一）：存储器模式：stm32作为主机对AT24C02写读数据
存储器模式：在HAL库中，I2C有专门对存储器外设设置的库函数 I2C（一）：存储器模式的使用 1、I2C轮询式写读AT24C02一页数据2、I2C轮询式写读AT24C02多页数据3、I2C中断式写读AT24C02一页数据4、I2C使用DMA式写读AT24C02一…...
AI助手网站
chatgpt ：https://chatgpt.com/ https://openai.com/index/chatgpt/ 百度ai助手 https://chat.baidu.com/ 百度AI助手https://chat.baidu.com/ 文心快码 文心快码BaiduComate 文心快码BaiduComate 文心快码BaiduComate有代码问题，问文…...
初始nginx
华子目录 nginx介绍nginx功能介绍基础特性web服务相关功能nginx进程结构web请求处理机制 nginx进程间通信nginx启动与http连接建立http处理过程 nginx模块介绍nginx命令演示 nginx介绍 nginx是免费的、开源的、高性能的HTTP和反向代理服务器、邮件代理服务器、以及TCP/UDP代理服…...
可扩展性设计架构模式——事件驱动架构
事件驱动架构（Event-Driven Architecture, EDA）是一种可扩展性设计软件架构模式，它通过事件来触发和通信（以事件为核心），实现不同系统组件之间的解耦（促进应用程序或系统部件之间的松耦合通信&a…...
Prometheus 专栏 —— Prometheus安装、配置
配置文件基本结构 global: 全局配置 scrape_interval: 抓取目标指标的频率，默认为 1minevaluation_interval: 评估告警规则的频率，默认为 1minscrape_timeout: 抓取目标指标数据拉取超时，默认为 10s，如果出现 context deadline e…...
Java并发编程面试题：线程池Fork/Join（19题）
🧑 博主简介：CSDN博客专家，历代文学网（PC端可以访问：https://literature.sinhy.com/#/?__c1000，移动端可微信小程序搜索“历代文学”）总架构师，15年工作经验，精通Java编…...
【每日学点鸿蒙知识】WebView代理、2D绘制矩形圆角、TextInput清理按钮、pdf滑动、icon配置问题
1、HarmonyOS Webview 支持设置代理功能吗？ 使用Web的onInterceptRequest先拦截再代理来实现。具体可以参考文档：https://developer.huawei.com/consumer/cn/doc/harmonyos-references-V5/ts-basic-components-web-V5#ZH-CN_TOPIC_0000001930757269__on…...
抽奖系统（1）（Java 实现）
1. 需求描述 1. 包含管理员的注册与登录 1) 注册包含：姓名、邮箱、手机号、密码 2) 登录包含两种方式 (1) 电话 密码登录 (2) 电话 短信登录；验证码获取 (3) 登录需要校验管理员身份 2. 人员管理：管理员支持创建普通用户，查看…...
数据库系统原理复习汇总
数据库系统原理复习汇总 一、数据库系统原理重点内容提纲 题型：主观题 1、简答题 第一章：数据库的基本概念：数据库、数据库管理系统、三级模式；两级映像、外码 第二章：什么是自然连接、等值连接； 第三…...
基于16QAM的载波同步和定时同步性能仿真,采用四倍采样,包括Costas环和gardner环
目录 1.算法仿真效果 2.算法涉及理论知识概要 3.MATLAB核心程序 4.完整算法代码文件获得 1.算法仿真效果 matlab2022a仿真结果如下（完整代码运行后无水印）： 仿真操作步骤可参考程序配套的操作视频。 2.算法涉及理论知识概要 载波同步是…...
鸿蒙next RCP网络请求工具类进阶版来了
前言： 各位同学大家好，有一段时间没有更新文章了,最近因为鸿蒙官方的网络请求换掉了了rcp 之前是使用http 这些都是原生开发的 当然有那种三方大家熟知的 axios (这个也是基于http 后面也会过时)所以大家还是要了解一下rcp的原生的网络请求的。那么我们…...
driftingblues6_vh靶机
首先把靶机换成NAT模式 使用 arp-scan 命令扫描网段内存活的主机，以获取靶机ip地址 arp-scn -l 尝试访问ip 使用御剑扫描子域名，尝试访问robots.txt文件 通过访问文件我们发现了一个/textpattern/textpattern目录 访问一下目录发现了登录页面 他还给了…...
Go语言入门
文章目录 零、Linux下Go的安装1.下载、解压2.添加环境变量3.验证安装4.初始化Go模块(1)cd到项目目录(2)初始化模块(3)获取依赖包(4)清理和验证依赖(5)检查 go.mod 文件(6)介绍 go.mod 和 go.sum 文件 5.项目目录结构 一、感性认识1.从 Hello world 开始2.加法函数 二、Go语法1.…...
VS Code中怎样查看某分支的提交历史记录
VsCode中无法直接查看某分支的提交记录，需借助插件才行，常见的插件如果git history只能查看某页面的改动记录，无法查看某分支的整体提交记录，我们可以安装GIT Graph插件来解决这个问题 1.在 VSCode的插件库中搜索 GIT Graph安装&a…...
【杂谈】-AI搜索引擎如何改变传统SEO及其在内容营销中的作用
AI搜索引擎如何改变传统SEO及其在内容营销中的作用 文章目录 AI搜索引擎如何改变传统SEO及其在内容营销中的作用1、什么是AI搜索引擎2、AI搜索引擎对SEO策略的影响3、AI搜索引擎在内容营销转型中的作用4、AI搜索引擎在营销领域的挑战、道德问题和未来5、总结 在当今的数字营销世…...