博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Tarjan 割边(桥)
阅读量:5901 次
发布时间:2019-06-19

本文共 1044 字,大约阅读时间需要 3 分钟。

//Tarjan 割边 //当dfn[u]
#include
#include
#include
#include
#include
using namespace std;int n,m,cnt,ans,head[10001];int dot,dfn[10001],low[10001];int cut[200001];struct uio{ int from,to,next,id;}edge[200001];void add(int x,int y){ edge[++cnt].next=head[x]; edge[cnt].from=x; edge[cnt].to=y; edge[cnt].id=cnt; head[x]=cnt;}void tarjan(int x,int fa){ dfn[x]=low[x]=++dot; for(int i=head[x];i;i=edge[i].next) { int y=edge[i].to; if(!dfn[y]) { tarjan(y,x); low[x]=min(low[x],low[y]); if(low[y]>dfn[x]) cut[edge[i].id]=1; } else if(y!=fa) low[x]=min(low[x],dfn[y]); }}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i); for(int i=1;i<=cnt;i++) if(cut[i]) ans++; printf("%d\n",ans); for(int i=1;i<=cnt;i++) if(cut[i]) printf("%d %d\n",edge[i].from,edge[i].to); return 0;}

 

转载于:https://www.cnblogs.com/water-radish/p/9280524.html

你可能感兴趣的文章
ubuntu下解决鼠标滚轮不能使用的问题
查看>>
隐马尔可夫(HMM)、前/后向算法、Viterbi算法 再次总结
查看>>
LAV Filters
查看>>
iOS11 automaticallyAdjustsScrollViewInsets和estimatedRowHeight适配
查看>>
订阅linux kernel的mail list
查看>>
mysql 批量更新多条记录(且不同值)的实现方法
查看>>
Hadoop上路_02-hadoop介绍和环境准备
查看>>
JFinal多参数搜索条件自动组装及参数传递
查看>>
c++ ios_base register_callback方法使用
查看>>
Java中为什么需要Object类,Object类为什么是所有类的父类
查看>>
css3 -webkit-flex 布局
查看>>
大数据Benchmark
查看>>
windows server2008多用户远程登陆设置方法
查看>>
sencha touch巧妙使用请求超时提升用户体验
查看>>
15. 3Sum
查看>>
ArrayList源码解析
查看>>
基于SpringMVC、Maven以及Mybatis的环境搭建
查看>>
angularjs-paste-upload
查看>>
RXjs相关
查看>>
linux基础命令 head
查看>>