tarjan求桥,算法流程详见核心代码:

 void tarjan(int k){
dfn[k]=low[k]=++cnt;
//fa[k]=(edge){f,0,fid};
for(int i=head[k];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
fa[v]=e[i].id;//标记该边已走过,防止沿无向边返回
tarjan(v);
low[k]=min(low[v],low[k]);
}else
if(fa[k]!=e[i].id)low[k]=min(low[k],dfn[v]);//在不走无向边的情况下更新low
}
if(fa[k]&&low[k]==dfn[k])//若节点k的low=dfn则k在一个联通块中处于搜索树的顶部,那么节点k的父边一定为割边
ans[++na]=fa[k];
}

模板题:zoj2588

题目大意:给出一个无向图,按顺序输出割边序号。

好久没用zoj,PE几次,若无割边要加个判断,以免多输出个0

 #include<cstring>
#include<cstdio>
#include<algorithm>
#define foru(i,x,y) for(int i=x;i<=y;i++)
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
const int N=;
struct edge{int to,nxt,id;}e[];
int head[N],dfn[N],low[N],ans[N],ne,na,cnt,n,m;
int fa[N];
void add(int a,int b,int c){
e[++ne]=(edge){b,head[a],c};head[a]=ne;
} void tarjan(int k){
dfn[k]=low[k]=++cnt;
//fa[k]=(edge){f,0,fid};
for(int i=head[k];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
fa[v]=e[i].id;//标记该边已走过,防止沿无向边返回
tarjan(v);
low[k]=min(low[v],low[k]);
}else
if(fa[k]!=e[i].id)low[k]=min(low[k],dfn[v]);//在不走无向边的情况下更新low
}
if(fa[k]&&low[k]==dfn[k])//若节点k的low=dfn则k在一个联通块中处于搜索树的顶部,那么节点k的父边一定为割边
ans[++na]=fa[k];
} int main(){
int T,u,v;
scanf("%d",&T);
while(T--){
clr(e);clr(head);clr(dfn);clr(low);clr(fa);clr(ans);
ne=na=cnt=;
scanf("%d%d",&n,&m);
foru(i,,m){
scanf("%d%d",&u,&v);
add(u,v,i);add(v,u,i);
}
foru(i,,n)
if(!dfn[i])tarjan(i);
sort(ans+,ans++na);
printf("%d\n",na);
if(na){
foru(i,,na-)printf("%d ",ans[i]);printf("%d\n",ans[na]);}
if(T)printf("\n");
}
return ;
}

最新文章

  1. &lt;转&gt;Unity3D研究院之C#使用Socket与HTTP连接服务器传输数据包
  2. mybatis批量插入返回主键问题
  3. RNN 入门教程 Part 3 – 介绍 BPTT 算法和梯度消失问题
  4. linux库列表
  5. linux下批量查找/替换文本内容
  6. jsp获取SessionID值
  7. Redis初步
  8. javascript算法挑战
  9. Qt的十六进制的控件
  10. 前端新人学习笔记-------html/css/js基础知识点(三)
  11. linux线程之pthread_join
  12. hdu2242(树形dp+tarjan+缩点)
  13. Bootstrap File Input的简单使用
  14. Python逻辑运算符
  15. css中单位px,em,rem和vh/vw的理解
  16. p1257 平面上最接近点对---(分治法)
  17. lumen----------A facade root has not been set.
  18. SQL注入之Sqli-labs系列第四十七关,第四十八关,第四十九关(ORDER BY注入)
  19. 浅谈C#堆栈与托管堆的工作方式(转)
  20. BZOJ3110 [Zjoi2013]K大数查询 树套树 线段树 整体二分 树状数组

热门文章

  1. C++ spdlog日志管理
  2. mysql的常见面试问题
  3. tomcat用户配置
  4. Linux-线程常见函数
  5. UML-领域模型-定义
  6. Java 实现 栈
  7. 【转】Rendering Problems The following classes could not be instantiated
  8. Vue专题-组件
  9. SVN的import和export的使用
  10. Linux-竟态初步引入