割边的tarjan算法
2024-09-05 22:17:08
与割点唯一一点不同是low[v]>=dfn[u]变为low[v]>dfn[u]
代码如下:
bool vis[maxn];
int dfn[maxn],low[maxn];
int cnt;
vector<int>gra[maxn];
void cutPoint(int u,int v){
vis[u]=true;
dfn[u]=low[u]=++cnt;
int child=0;
int sz=gra[u].size();
for(int i=0;i<sz;i++){
int v=gra[u][i];
if(v!=f&&vis[v]){
low[u]=min(low[u],dfn[v]);
}else if(!vis[v]){
child++;
cutPoint(u,v);
low[u]=min(low[u],low[v]);
if(f!=-1&&low[v]>dfn[u]){
printf("%d-%d\n",u,v);
}
}
}
}
最新文章
- MySQL/MariaDB/PerconaDB-提权条件竞争漏洞
- 按键的使用(一)------verilog
- 有关对字符串的处理,需要用到List时的简化写法
- Java--常用类summary(二)
- Hdu 1521 排列组合
- ajax请求总是不成功?浏览器的同源策略和跨域问题详解
- 《HTML5 and Javascript Web Apps》读书笔记要点摘录
- hadoop 学习笔记 (十) mapreduce2.0
- Imatest 崩溃
- cf467A George and Accommodation
- OpenCVR 有新成员 OpenCVV OpenCVC
- 前端学习笔记(zepto或jquery)——对li标签的相关操作(一)
- 【最新版】从零开始在 macOS 上配置 Lua 开发环境
- Educational Codeforces Round 2_B. Queries about less or equal elements
- 微信公众平台开发,图文回复、access_token生成调用、以及微信SDK的实现(2)
- PHP 序列化/反序列化的方法函数
- xshell连不上虚拟机
- 记录4-Ubuntu 16.04用gparted调整分区
- WEB测试重点--(转载)
- python之匿名函数lambda